题面

题目传送

题目描述

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

输入格式

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

输出格式

两行分别输出最小总效益和最大总效益。

思路

裸的二分图最佳完美匹配，这里用费用流解决。

需要注意的是求最大值的情况可以用小技巧，将边权取相反数，求出的费用再次取相反数即可。

代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
long long n,last[200005],to[200005],nextt[200005],s[200005],t[200005],top=1,ans=0,cost=0;
long long d[200005];
long long v[200005];
struct path{
    long long from,edge;
};
path p[200005];
void add(int a,int b,int c,int d){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    t[top]=d;
    last[a]=top;
}
bool spfa(long long S,long long T){
    queue<long long> q;
    memset(v,0,sizeof(v));
    memset(d,63,sizeof(d));
    memset(p,-1,sizeof(p));
    q.push(S);
    v[S]=1;
    d[S]=0;
    d[T]=2147483647;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        for (int i=last[now];i;i=nextt[i]){
            long long j=to[i];
            if (s[i]<=0){
                continue;
            }
            if (d[now]+t[i]<d[j]){
                d[j]=d[now]+t[i];
                p[j].from=now;
                p[j].edge=i;
                if (!v[j]){
                    q.push(j);
                    v[j]=1;
                }
            }
        }
        v[now]=0;
    }
    if (d[T]<2147483647){
        return 1;
    }else{
        return 0;
    }
}
void EK(long long S,long long T){
    while (spfa(S,T)){
        long long minn=2147483647;
        for (int i=T;i!=S;i=p[i].from){
            minn=min(minn,s[p[i].edge]);
        }
        ans+=minn;
        for (int i=T;i!=S;i=p[i].from){
            s[p[i].edge]-=minn;
            s[p[i].edge^1]+=minn;
        }
        cost+=minn*d[T];
    }
}
int main(){
    long long S=205,T=206;
    cin>>n;
    int a[105][105];
    for (int i=1;i<=n;i++){
    	for (int j=1;j<=n;j++){
    		a[i][j]=read();
		}
	}
	for (int i=1;i<=n;i++){
		add(S,i,1,0);
		add(i,S,0,0);
		add(n+i,T,1,0);
		add(T,n+i,0,0);
		for (int j=1;j<=n;j++){
			add(i,n+j,1,a[i][j]);
			add(n+j,i,0,-a[i][j]);
		}
	}
    EK(S,T);
    cout<<cost<<endl;
    memset(last,0,sizeof(last));
    memset(to,0,sizeof(to));
    memset(nextt,0,sizeof(nextt));
    memset(s,0,sizeof(s));
    memset(t,0,sizeof(t));
    memset(d,0,sizeof(d));
    memset(v,0,sizeof(v));
    memset(p,0,sizeof(p));
    top=1;cost=0;ans=0;
	for (int i=1;i<=n;i++){
		add(S,i,1,0);
		add(i,S,0,0);
		add(n+i,T,1,0);
		add(T,n+i,0,0);
		for (int j=1;j<=n;j++){
			add(i,n+j,1,-a[i][j]);
			add(n+j,i,0,a[i][j]);
		}
	}
    EK(S,T);
    cout<<-cost<<endl;
}