这个题目，建图我是按
源点->(有流量无费用)->人->(无穷的流量有费用)->仓库->(有流量无费用)->汇点
建图没弄好wa了一次。剩下就是模版了。。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define INF 0x7fffffff 7 8 int pd[51][51]; 9 int im[51][51]; 10 int cc[51][51][51]; 11 12 int low[1001],path[1001]; 13 int first[1001],in[1001],dis[1001]; 14 int str,end,t; 15 struct node 16 { 17 int u,v,w,cost,re,next; 18 }edge[101*101]; 19 int sp,cf; 20 void CL() 21 { 22 t = 1; 23 memset(first,-1,sizeof(first)); 24 } 25 void add(int u,int v,int w,int cost) 26 { 27 edge[t].u = u; 28 edge[t].v = v; 29 edge[t].w = w; 30 edge[t].cost = cost; 31 edge[t].re = t+1; 32 edge[t].next = first[u]; 33 first[u] = t ++; 34 35 edge[t].u = v; 36 edge[t].v = u; 37 edge[t].w = 0; 38 edge[t].cost = -cost; 39 edge[t].re = t-1; 40 edge[t].next = first[v]; 41 first[v] = t ++; 42 } 43 int bfs() 44 { 45 int u,i,v; 46 memset(path,-1,sizeof(path)); 47 for(i = 0;i <= end;i ++) 48 { 49 dis[i] = INF; 50 in[i] = 0; 51 } 52 queue que; 53 que.push(str); 54 dis[str] = 0; 55 in[str] = 1; 56 low[str] = INF; 57 while(!que.empty()) 58 { 59 u = que.front(); 60 in[u] = 0; 61 que.pop(); 62 for(i = first[u];i != -1;i = edge[i].next) 63 { 64 v = edge[i].v; 65 if(edge[i].w&&dis[v] > dis[u]+edge[i].cost) 66 { 67 dis[v] = dis[u] + edge[i].cost; 68 path[v] = i; 69 low[v] = low[u] < edge[i].w ? low[u]:edge[i].w; 70 if(!in[v]) 71 { 72 que.push(v); 73 in[v] = 1; 74 } 75 } 76 } 77 } 78 if(path[end] == -1) 79 return -1; 80 else 81 return low[end]; 82 83 } 84 void mcmf() 85 { 86 int res,temp,now; 87 while((res = bfs()) != -1) 88 { 89 now = end; 90 cf += res; 91 while(now != str) 92 { 93 temp = path[now]; 94 edge[temp].w -= res; 95 edge[edge[temp].re].w += res; 96 sp += res*edge[temp].cost; 97 now = edge[temp].u; 98 } 99 }100 }101 int main()102 {103 int n,m,k,u,ans,sum,i,j;104 while(scanf("%d%d%d",&n,&m,&k)!=EOF)105 {106 if(!n&&!m&&!k) break;107 for(i = 1;i <= n;i ++)108 {109 for(j = 1;j <= k;j ++)110 scanf("%d",&pd[i][j]);111 }112 for(i = 1;i <= m;i ++)113 {114 for(j = 1;j <= k;j ++)115 scanf("%d",&im[i][j]);116 }117 for(i = 1;i <= k;i ++)118 {119 for(j = 1;j <= n;j ++)120 {121 for(u = 1;u <= m;u ++)122 scanf("%d",&cc[i][j][u]);123 }124 }125 str = 0;126 end = n+m+1;127 ans = 0;128 for(i = 1;i <= k;i ++)129 {130 CL();131 sum = 0;132 for(j = 1;j <= n;j ++)133 {134 add(str,j,pd[j][i],0);135 sum += pd[j][i];136 }137 for(j = 1;j <= m;j ++)138 add(n+j,end,im[j][i],0);139 for(j = 1;j <= n;j ++)140 {141 for(u = 1;u <= m;u ++)142 add(j,n+u,INF,cc[i][j][u]);143 }144 sp = cf = 0;145 mcmf();146 if(cf < sum) break;147 ans += sp;148 }149 if(i == k+1)150 printf("%d\n",ans);151 else152 printf("-1\n");153 }154 return 0;155 }