有 nn 件工作要分配给 nn 个人做。第 ii 个人做第 jj 件工作产生的效益为 c_{ij}cij? 。试设计一个将 nn 件工作分配给 nn 个人做的分配方案，使产生的总效益最大。
输入格式：
文件的第 11 行有 11 个正整数 nn，表示有 nn 件工作要分配给 nn 个人做。
接下来的 nn 行中，每行有 nn 个整数 c_{ij}cij???，表示第 ii 个人做第 jj 件工作产生的效益为 c_{ij}cij?。
输出格式：
两行分别输出最小总效益和最大总效益。
1 \leq n \leq 1001≤n≤100
一个人只能修一个工件
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #define N 1010100 using namespace std; int n,m,S,T,head[N],tot; struct node{ int to,next,flow,w; }e[N]; int dis[N],flow[N],pre[N],last[N],cost; bool vis[N]; queue<int>Q; struct MCMFF{ void init(){ tot=-1,cost=0; memset(head,-1,sizeof(head)); memset(e,0,sizeof(e)); } void add(int u,int v,int flow,int w){ e[++tot].to=v,e[tot].next=head[u],head[u]=tot,e[tot].w=w,e[tot].flow=flow; } void Add(int u,int v,int flow,int w){ add(u,v,flow,w); add(v,u,0,-w); } bool spfa() { memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis)); memset(flow,0x7f,sizeof(flow)); Q.push(S);vis[S]=1,pre[T]=-1,dis[S]=0; while(!Q.empty()){ int u=Q.front();Q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].to; if(e[i].flow>0&&dis[v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; pre[v]=u,last[v]=i; flow[v]=min(flow[v],e[i].flow); if(!vis[v]){ Q.push(v); vis[v]=1; } } } }return pre[T]!=-1; } void MCMF(){ while(spfa()){ int u=T; cost+=flow[T]*dis[T]; while(u!=S){ e[last[u]].flow-=flow[T]; e[last[u]^1].flow+=flow[T]; u=pre[u]; } } } }netfl; int work[105][105]; int main() { scanf("%d",&n); netfl.init(); S=0,T=2*n+1; for(int i=1;i<=n;i++){ netfl.Add(S,i,1,0); netfl.Add(i+n,T,1,0); for(int j=1;j<=n;j++){ scanf("%d",&work[i][j]); netfl.Add(i,j+n,1,work[i][j]); } } netfl.MCMF(); printf("%d\n",cost); netfl.init(); for(int i=1;i<=n;i++){ netfl.Add(S,i,1,0); netfl.Add(i+n,T,1,0); for(int j=1;j<=n;j++){ netfl.Add(i,j+n,1,-1*work[i][j]); } } netfl.MCMF(); printf("%d\n",-1*cost); return 0; }
原文：https://www.cnblogs.com/song-/p/9549988.html