网络流24题之十八 分配问题
填坑
地址:cv1915
题目描述 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
模型
二分图最佳匹配问题,可以费用流解决(或KM算法)。
实现
把所有人看做二分图中顶点Xi,所有工作看做二分图中顶点Yi,建立附加源S汇T。
1、从S向每个Xi连一条容量为1,费用为0的有向边。
2、从每个Yi向T连一条容量为1,费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大,费用为Cij的有向边。
求最小费用最大流,最小费用流值就是最少运费,求最大费用最大流,最大费用流值就是最多运费。
分析
二分图最佳匹配建模方法为费用流模型。
代码
#include <cstdio> #include <algorithm> #include <queue> #include <map> #include <string> #include <cstring> #include <iostream> #define M 50000 #define N 500 #define INF 0x33333333 #define min(x,y) ((x<y)?(x):(y)) using namespace std; typedef pair<int,int> Pair; map <string,int>ma; struct node{int from,to,next,flow,cost;}e[M]; int tot=-1,st[M]; int n,m,x,y,z; int pe[N],pv[N],dis[N],vis[N]; void add(int x,int y,int z,int zz){ e[++tot].to=y; e[tot].from=x; e[tot].flow=z; e[tot].cost=zz; e[tot].next=st[x]; st[x]=tot; } void add_edge(int x,int y,int z,int zz){add(x,y,z,zz),add(y,x,0,-zz);} queue<int>que; bool maxspfa(int S,int T) { for (int i=S;i<=T;i++) dis[i]=-INF; memset(vis,0,sizeof vis); que.push(S),vis[S]=1,dis[S]=0; while(!que.empty()) { int now=que.front();que.pop();vis[now]=0; for (int i=st[now];~i;i=e[i].next) if (e[i].flow>0 && dis[e[i].to]<dis[now]+e[i].cost) { dis[e[i].to]=dis[now]+e[i].cost; pe[e[i].to]=i,pv[e[i].to]=now; if (!vis[e[i].to]) vis[e[i].to]=1,que.push(e[i].to); } } return dis[T]!=-INF; } Pair mfmaxc(int S,int T) { int COST=0,FLOW=0,flow; while(maxspfa(S,T)) { flow=0x3f3f3f3f; for (int i=T;i!=S;i=pv[i]) flow=min(flow,e[pe[i]].flow); COST+=flow*dis[T]; FLOW+=flow; for (int i=T;i!=S;i=pv[i]) e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow; } return make_pair(FLOW,COST); } bool minspfa(int S,int T) { memset(dis,0x33,sizeof dis); memset(vis,0,sizeof vis); que.push(S),vis[S]=1,dis[S]=0; while(!que.empty()) { int now=que.front();que.pop();vis[now]=0; for (int i=st[now];~i;i=e[i].next) if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].cost) { dis[e[i].to]=dis[now]+e[i].cost; pe[e[i].to]=i,pv[e[i].to]=now; if (!vis[e[i].to]) vis[e[i].to]=1,que.push(e[i].to); } } return dis[T]<INF; } Pair mfminc(int S,int T) { int COST=0,FLOW=0,flow; while(minspfa(S,T)) { flow=INF; for (int i=T;i!=S;i=pv[i]) flow=min(flow,e[pe[i]].flow); COST+=flow*dis[T]; FLOW+=flow; for (int i=T;i!=S;i=pv[i]) e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow; } return make_pair(FLOW,COST); } main() { memset(st,-1,sizeof st); memset(e,-1,sizeof e); scanf("%d",&n); int S=0,T=n+n+1,cost[N][N]; for (int i=1;i<=n;i++) add_edge(S,i,1,0); for (int i=1;i<=n;i++) add_edge(i+n,T,1,0); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&cost[i][j]),add_edge(i,j+n,INF,cost[i][j]); Pair ans=mfminc(S,T); printf("%d\n",ans.second); memset(st,-1,sizeof st); memset(e,-1,sizeof e); for (int i=1;i<=n;i++) add_edge(S,i,1,0); for (int i=1;i<=n;i++) add_edge(i+n,T,1,0); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) add_edge(i,j+n,INF,cost[i][j]); ans=mfmaxc(S,T); printf("%d",ans.second); }