【网络流24题】分配问题

Description

有n件工作要分配给n个人做。第i 个人做第j 件工作产生的效益为ij c 。试设计一个将n件工作分配给n个人做的分配方案，使产生的总效益最大。
对于给定的n件工作和n个人，计算最优分配方案和最差分配方案。

Input

第1 行有1 个正整数n，表示有n件工作要分配给n 个人做。
接下来的n 行中，每行有n 个整数ij c ，1≤i≤n，1≤j≤n，表示第i 个人做第j件工作产生的效益为ij c 。

Output

将计算出的最小总效益和最大总效益输出

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

Hint

数据范围：
N<=100

Source

网络流
二分图最佳匹配，最小费用最大流

当费用流练手题吧。。。好久没打了。（好像不用费用流。。。）S向工作,人向T连w=1,cost=0的边，然后工作a向人b连w=1,cost=c[i][j]的边，跑费用流，输出。。。所有边权×=-1，再跑一遍。。。

 1 // It is made by XZZ
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 #define rep(a,b,c) for(rg int a=b;a<=c;a++)
 7 #define drep(a,b,c) for(rg int a=b;a>=c;a--)
 8 #define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
 9 #define il inline
10 #define rg register
11 #define vd void
12 #define t (dis[i])
13 typedef long long ll;
14 il int gi(){
15     rg int x=0;rg char ch=getchar();
16     while(ch<'0'||ch>'9')ch=getchar();
17     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
18     return x;
19 }
20 const int maxn=101+101+10,maxm=(101*101+100)<<1,S=1,T=2;
21 int fir[maxn],dis[maxm],nxt[maxm],w[maxm],cost[maxm],id=1;
22 il vd add(int a,int b,int W,int C){
23     nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=W,cost[id]=C;
24     if(W)add(b,a,0,-C);
25 }
26 int nw[101],np[101];
27 il bool Super_Fast(int&Cost){
28     int que[maxn],hd=0,tl=1,Dis[maxn],last[maxn]={0};bool inque[maxn]={0};
29     memset(Dis,127/3,sizeof Dis);Dis[S]=0;
30     que[0]=S,inque[S]=1;
31     while(hd^tl){
32     int now=que[hd];hd=(hd+1)%maxn,inque[now]=0;
33     erep(i,now)
34         if(Dis[now]+cost[i]<Dis[t]&&w[i]){
35         Dis[t]=Dis[now]+cost[i],last[t]=i;
36         if(!inque[t])que[tl++]=t,inque[t]=1,tl%=maxn;
37         }
38     }
39     if(!last[T])return false;
40     rg int flow=666666666;
41     for(rg int i=last[T];i;i=last[dis[i^1]])flow=min(flow,w[i]);
42     for(rg int i=last[T];i;i=last[dis[i^1]])w[i]-=flow,w[i^1]+=flow,Cost+=cost[i]*flow;
43     return true;
44 }
45 il int mincost(int Cost=0){
46     while(Super_Fast(Cost));
47     return Cost;
48 }
49 int main(){
50     int n=gi();
51     rep(i,1,n)nw[i]=i+2,add(S,nw[i],1,0);
52     rep(i,1,n)np[i]=i+n+2,add(np[i],T,1,0);
53     rep(i,1,n)rep(j,1,n)add(nw[i],np[j],1,gi());
54     printf("%d
",mincost());
55     rep(i,2,id)w[i]=1-(i&1),cost[i]*=-1;
56     printf("%d
",-mincost());
57     return 0;
58 }

View Code