题目描述 Description
有n件工作要分配给n个人做。第i 个人做第j 件工作产生的效益为ij c 。试设计一个将
n件工作分配给n个人做的分配方案，使产生的总效益最大。
«编程任务：
对于给定的n件工作和n个人，计算最优分配方案和最差分配方案。
输入描述 Input Description
第1 行有1 个正整数n，表示有n件工作要分配给n 个人做。接下来的n 行中，每行有n 个整数 cij ，1≤i≤n，1≤j≤n，表示第i 个人做第j件工作产生的效益为cij
输出描述 Output Description
将计算出的最小总效益和最大总效益输出
样例输入 Sample Input
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
样例输出 Sample Output
5
14
思路：费用流
有关数据规模 n<=100差不多就够了。
代码实现：
1 #include<cstdio> 2 #include<cstring> 3 #define maxn 110 4 #define INF 2139062143 5 int n,s,t,up,down; 6 int a; 7 long long la,lb; 8 int map[maxn][maxn]; 9 int w[maxn],p[maxn][2]; 10 int head,tail,q[maxn*maxn*3]; 11 int h[maxn],hs; 12 struct edge{int s,n,w,f,r;}e[maxn*maxn*3]; 13 void ap(int k){ 14 if(k==s) return; 15 ap(p[k][1]); 16 e[p[k][0]].w--; 17 e[e[p[k][0]].r].w++; 18 } 19 void SPFA(){ 20 memset(w,0x7f,sizeof(w)); 21 head=tail=0; 22 q[head++]=s,w[s]=0; 23 while(head>tail){ 24 a=q[tail++]; 25 for(int i=h[a];i;i=e[i].n) 26 if(e[i].w){ 27 la=e[i].f,lb=w[a],la+=lb,lb=w[e[i].s]; 28 if(la<lb){ 29 w[e[i].s]=la; 30 p[e[i].s][0]=i; 31 p[e[i].s][1]=a; 32 q[head++]=e[i].s; 33 } 34 } 35 } 36 } 37 bool D_small(){ 38 SPFA(); 39 if(w[t]==INF) return 0; 40 ap(t); 41 down+=w[t]; 42 return 1; 43 } 44 bool D_big(){ 45 SPFA(); 46 if(w[t]==INF) return 0; 47 ap(t); 48 up+=-w[t]; 49 return 1; 50 } 51 int main(){ 52 scanf("%d",&n); 53 s=0,t=2*n+1; 54 for(int i=1;i<=n;i++) 55 for(int j=1;j<=n;j++){ 56 scanf("%d",&map[i][j]); 57 e[++hs]=(edge){j+n,h[i],1,map[i][j],hs+1},h[i]=hs; 58 e[++hs]=(edge){i,h[j+n],0,-map[i][j],hs-1},h[j+n]=hs; 59 } 60 for(int i=1;i<=n;i++) e[++hs]=(edge){i,h[0],1,0},h[0]=hs; 61 for(int i=1;i<=n;i++) e[++hs]=(edge){t,h[i+n],1,0},h[i+n]=hs; 62 while(D_small()); 63 memset(e,0,sizeof(e)); 64 memset(h,0,sizeof(h)); 65 hs=0; 66 for(int i=1;i<=n;i++) 67 for(int j=1;j<=n;j++){ 68 e[++hs]=(edge){j+n,h[i],1,-map[i][j],hs+1},h[i]=hs; 69 e[++hs]=(edge){i,h[j+n],0,map[i][j],hs-1},h[j+n]=hs; 70 } 71 for(int i=1;i<=n;i++) e[++hs]=(edge){i,h[0],1,0},h[0]=hs; 72 for(int i=1;i<=n;i++) e[++hs]=(edge){t,h[i+n],1,0},h[i+n]=hs; 73 while(D_big()); 74 printf("%d %d ",down,up); 75 return 0; 76 }
看来没有直接求最长路径的算法。
题目来源：CODE[VS]