问题描述
有 n件工作要分配给 n个人做。第 i 个人做第 j 件工作产生的效益为c[i,j] 。试设计一个将n 件工作分配给 n个人做的分配方案，使产生的总效益最大。
编程任务
对于给定的 n件工作和 n 个人，计算最优分配方案和最差分配方案。
数据输入
输入的第 1 行有 1 个正整数 n，表示有 n件工作要分配给 n 个人做。接下来的 n 行中，每行有 n 个整数c[i,j]，1≤i≤n，1≤j≤n，表示第 i 个人做第 j 件工作产生的效益为c[i,j] 。
结果输出
程序运行结束时，输出最小总效益和最大总效益。 输入文件示例5
2 2 2 1 2
2 3 1 2 4
2 0 1 1 1
2 3 4 3 3
3 2 1 2 1
输出文件示例
5 14
把所有人看做二分图中顶点Xi，所有工作看做二分图中顶点Yi，建立附加源S汇T。1、从S向每个Xi连一条容量为1，费用为0的有向边。2、从每个Yi向T连一条容量为1，费用为0的有向边。3、从每个Xi向每个Yj连接一条容量为无穷大，费用为Cij的有向边。求最小费用最大流，最小费用流值就是最少运费，求最大费用最大流，最大费用流值就是最多运费。
具体实现方法见
代码：
1 const 2 maxn=100000000; 3 4 var 5 ot,ot1,ne1,cap1,ne,cap,h:array[0..30000]of longint; 6 cost,cost1:array[0..30000,1..2]of longint; 7 g,g1,pre,dis:array[0..1010]of longint; 8 inq:array[0..1010]of boolean; 9 e,s,t,c,i,n,m,ans,j:longint;10 11 procedure addedge(x,y,z,w:longint);12 begin13 ot[e]:=y; ne[e]:=g[x]; cap[e]:=z; cost[e,1]:=w; cost[e,2]:=-w; g[x]:=e; inc(e);14 ot[e]:=x; ne[e]:=g[y]; cap[e]:=0; cost[e,1]:=-w; cost[e,2]:=w; g[y]:=e; inc(e);15 end;16 17 function min(a,b:longint):longint;18 begin19 if a-1 do35 begin36 y:=ot[p];37 if (cap[p]>0)and(dis[y]>dis[x]+cost[p,c])38 then begin39 dis[y]:=dis[x]+cost[p,c]; pre[y]:=p;40 if inq[y]=false41 then begin inq[y]:=true; inc(r); h[r]:=y; end;42 end;43 p:=ne[p];44 end;45 inq[x]:=false;46 end;47 exit(dis[t]<>maxn);48 end;49 50 function find_path(c:longint):longint;51 var52 x,p,tmp,path:longint;53 begin54 x:=t; path:=maxn; tmp:=0;55 while x>s do56 begin57 p:=pre[x];58 path:=min(path,cap[p]);59 x:=ot[p xor 1];60 end;61 x:=t;62 while x>s do63 begin64 p:=pre[x];65 inc(tmp,path*cost[p,c]);66 inc(cap[p xor 1],path);67 dec(cap[p],path);68 x:=ot[p xor 1];69 end;70 exit(tmp);71 end;72 73 begin74 e:=0;75 fillchar(g,sizeof(g),255);76 readln(n);77 s:=0; t:=2*n+1; ans:=0;78 for i:=1 to n do79 begin addedge(s,i,1,0); addedge(n+i,t,1,0); end;80 for i:=1 to n do81 for j:=1 to n do82 begin83 read(c);84 addedge(i,n+j,maxn,c);85 end;86 g1:=g; ot1:=ot; cap1:=cap; ne1:=ne; cost1:=cost;87 while spfa(1) do88 inc(ans,find_path(1));89 writeln(ans);90 ans:=0;91 g:=g1; ot:=ot1; cap:=cap1; ne:=ne1; cost:=cost1;92 while spfa(2) do93 inc(ans,find_path(2));94 writeln(-ans);95 end.