题目描述
有 n 件工作要分配给 n 个人做。第 i个人做第 j 件工作产生的效益为cij 。试设计一个将 n件工作分配给 n 个人做的分配方案，使产生的总效益最大。
输入格式
文件的第 1 行有 1 个正整数 n，表示有 n 件工作要分配给 n 个人做。
接下来的 n 行中，每行有 n 个整数 cij，表示第 i 个人做第 j件工作产生的效益为cij。
输出格式
两行分别输出最小总效益和最大总效益。
输入输出样例
输入 #1
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
输出 #1
5 14
说明/提示
1 leq n leq 1001≤n≤100
一个人只能修一个工件
1 #include<bits/stdc++.h> 2 #define N 505 3 #define INF LLONG_MAX/2 4 using namespace std; 5 typedef struct 6 { 7 int u,v; 8 long long flow,cost;//flow 是流量 cost是花费 9 }ss; 10 ss edg[N*N]; 11 vector<int>edges[N];//记录每个点 所有和他相连的边吗 12 int now_edges=0;//等同于sumedg 13 14 void addedge(int u,int v,long long flow,long long cost) 15 { 16 edges[u].push_back(now_edges); 17 edg[now_edges++]=(ss){u,v,flow,cost}; 18 edges[v].push_back(now_edges); 19 edg[now_edges++]=(ss){v,u,0,-cost}; 20 } 21 22 bool spfa(int s,int t,long long &flow,long long &cost) 23 { 24 // printf("%lld %lld ",flow,cost); 25 long long dis[N]; 26 for(int i=0;i<N;i++)dis[i]=INF; 27 dis[s]=0; 28 int vis[N]={0}; 29 vis[s]=1; 30 queue<int>q; 31 q.push(s); 32 int pre[N]={0}; // 记录费用流路径的 记录前驱用的 通过前驱找到路径 然后最后会修改这个路径 33 long long maxflow[N]={0}; 34 maxflow[s]=INF; 35 36 while(!q.empty()) 37 { 38 int now=q.front(); 39 q.pop(); 40 vis[now]=0; 41 42 int Size=edges[now].size(); 43 for(int i=0;i<Size;i++) 44 { 45 ss &e=edg[edges[now][i]]; 46 47 if(e.flow>0&&dis[e.v]>dis[now]+e.cost) 48 { 49 dis[e.v]=dis[now]+e.cost; 50 pre[e.v]=edges[now][i]; 51 maxflow[e.v]=min(maxflow[now],e.flow); 52 53 if(!vis[e.v]) 54 { 55 q.push(e.v); 56 vis[e.v]=1; 57 } 58 } 59 } 60 } 61 62 if(dis[t]==INF)return false; 63 64 flow+=maxflow[t]; 65 cost+=dis[t]*maxflow[t]; 66 67 long long now=t; 68 while(now!=s) 69 { 70 edg[pre[now]].flow-=maxflow[t]; 71 edg[pre[now]^1].flow+=maxflow[t]; 72 now=edg[pre[now]].u; 73 } 74 75 76 return true; 77 } 78 79 void mcmf(int s,int t,long long &flow,long long &cost) 80 { 81 while(spfa(s,t,flow,cost)); //一次只能找到一条路径 但是费用流不止一条路径 把全部跑出来 82 } 83 void init() 84 { 85 now_edges=0; 86 for(int i=0;i<N;i++)edges[i].clear(); 87 } 88 89 int c[505][505]; 90 91 int main() 92 { 93 int n,s,t; 94 scanf("%d",&n); 95 s=2*n+1; 96 t=2*n+2; 97 for(int i=1;i<=n;i++) 98 for(int j=1;j<=n;j++) 99 { 100 scanf("%d",&c[i][j]); 101 } 102 103 104 for(int i=1;i<=n;i++) 105 for(int j=1;j<=n;j++)addedge(i,j+n,1,c[i][j]);//最短路跑 正边权跑最小费用 106 107 for(int i=1;i<=n;i++) 108 { 109 addedge(s,i,1,0); 110 addedge(i+n,t,1,0); 111 } 112 long long flow=0,cost=0; 113 mcmf(s,t,flow,cost); 114 printf("%lld ",cost); 115 116 init(); 117 118 for(int i=1;i<=n;i++) 119 for(int j=1;j<=n;j++)addedge(i,j+n,1,-c[i][j]);//负边权跑最大费用 120 121 for(int i=1;i<=n;i++) 122 { 123 addedge(s,i,1,0); 124 addedge(i+n,t,1,0); 125 } 126 flow=0; 127 cost=0; 128 mcmf(s,t,flow,cost); 129 printf("%lld ",-cost); 130 return 0; 131 }