分配问题（最小费用最大流）

article/2025/9/28 19:20:47

题目：有 n 件工作要分配给 n 个人做。第 i个人做第 j件工作产生的效益为。试设计一个将 n件工作分配给 n个人做的分配方案，使产生的总效益最大。

分析：这是一道多解法问题，可以用带剪枝的搜索和图论的最小费用最大流的方法来做，本文才去最小费用最大流的方法进行解决。

思路：

设立一个源点（2n+1）和汇点（2n+2），建图，

以源点(2n+1)向每个人 $i(1\leq i\leqslant n)$ 分别连边，每条边容量cap是1，费用cost为0，

再让每个人 $i(1\leq i\leqslant n)$ 向每件工作 $j+n(1\leq j\leqslant n)$ 分别连边，每条边容量是1，费用为 $c[i][j]$

最后让每件工作 $j+n(1\leq j\leqslant n)$ 向汇点（2n+2）连边，每条边容量是1，费用为0；

建图完毕后对改图跑最小费用最大流即可，求最小值可直接用最小费用最大流，求最大值则重新建图，将费用全部置为-cost，最大费用即为-ans。

AC代码：

/*author:wuzx*/#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<utility>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<iterator>
#include<iomanip>
#include<stack>
#include<cstdio>
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
using namespace std;
typedef unsigned long long ull;
const int maxn = 210;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
using namespace std;
ll c[maxn][maxn];
struct Edge{ll from,to,cap,flow,cost;
};
struct MCMF{int n,m;vector<Edge> edge;vector<int> g[maxn];int inq[maxn];int d[maxn];int p[maxn];int a[maxn];void init(int n){this->n=n;for(int i=0;i<maxn;i++)g[i].clear();edge.clear();}void add(int from,int to,int cap,int cost){edge.push_back(Edge{from,to,cap,0,cost});edge.push_back(Edge{to,from,0,0,-cost});m=edge.size();g[from].push_back(m-2);g[to].push_back(m-1);}bool BellmanFord(int s,int t,int& flow,ll& cost){for (int i = 0; i < maxn; i++)d[i] = inf;memset(inq,0,sizeof inq);d[s]=0;inq[s]=1;p[s]=0;a[s]=inf;queue<int> q;q.push(s);while(!q.empty()){int u=q.front();q.pop();inq[u]=0;for(int i=0;i<g[u].size();i++){Edge& e=edge[g[u][i]];if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){d[e.to]=d[u]+e.cost;p[e.to]=g[u][i];a[e.to]=min(a[u],e.cap-e.flow);if(!inq[e.to]){q.push(e.to);inq[e.to]=1;}}}}if(d[t]==inf)return false;cost+=d[t]*a[t];flow+=a[t];int u=t;while(u!=s){edge[p[u]].flow+=a[t];edge[p[u]^1].flow-=a[t];u=edge[p[u]].from;}return true;}ll MincostMaxflow(int s,int t,ll& cost){ll flow=0;cost=0;while(BellmanFord(s,t,flow,cost));return flow;}
};
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//    freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);int s,t,n;cin>>n;s=2*n+1,t=2*n+2;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>c[i][j];MCMF slove;slove.init(n);ll cc=0;for(int i=1;i<=n;i++)slove.add(s,i,1,0);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)slove.add(i,n+j,1,c[i][j]);for(int i=1;i<=n;i++)slove.add(i+n,t,1,0);slove.MincostMaxflow(s,t,cc);cout<<cc<<endl;MCMF slove1;slove1.init(n);for(int i=1;i<=n;i++)slove1.add(s,i,1,0);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)slove1.add(i,n+j,1,-c[i][j]);for(int i=1;i<=n;i++)slove1.add(i+n,t,1,0);slove1.MincostMaxflow(s,t,cc);cout<<-cc<<endl;return 0;
}