分配问题

题目复制乱码，就不复制了。

链接：落谷 P4014

很裸的一道二分图权值匹配，所以我们可以采用 KM 算法求解，但是我们还有一个更简单的算法，那就是费用流求解，我们建立一个超级源点S，和一个超级汇点T,让S连向人，让任务连向T，且费用都为0，流量为1.

然后根据输入的数据，对人和任务连线即可，就没了。。。。。

这道题数据很小就不用 ZKW 了，EK即可。。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=210,M=N*N*2;
int n,g[N][N],s,t,d[N];
int head[N],nex[M],w[M],to[M],fl[M],tot=1;
struct node{
	int v,e;
}p[M];
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; fl[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
int spfa(int k){
	int vis[N]={0};	queue<int> q;	q.push(s);	vis[s]=1;
	if(k)	memset(d,0xcf,sizeof d);
	else	memset(d,0x3f,sizeof d);	d[s]=0;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(k){
				if(d[to[i]]<d[u]+w[i]&&fl[i]){
					d[to[i]]=d[u]+w[i];
					p[to[i]].v=u;	p[to[i]].e=i;
					if(!vis[to[i]])	vis[to[i]]=1,q.push(to[i]);
				}
			}else{
				if(d[to[i]]>d[u]+w[i]&&fl[i]){
					d[to[i]]=d[u]+w[i];
					p[to[i]].v=u;	p[to[i]].e=i;
					if(!vis[to[i]])	vis[to[i]]=1,q.push(to[i]);
				}
			}
		}
	}
	if(k)	return d[t]!=0xcfcfcfcfcfcfcfcf;
	else	return d[t]!=0x3f3f3f3f3f3f3f3f;
}
int EK(int k){
	int res=0;
	while(spfa(k)){
		int mi=0x3f3f3f3f;
		for(int i=t;i!=s;i=p[i].v)	mi=min(mi,fl[p[i].e]);
		for(int i=t;i!=s;i=p[i].v){
			fl[p[i].e]-=mi;	fl[p[i].e^1]+=mi;
		}
		res+=d[t];
	}
	return res;
}
signed main(){
	cin>>n;	s=0; t=n*2+1;
	for(int i=1;i<=n;i++)	add(s,i,1,0),add(i+n,t,1,0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>g[i][j];	add(i,j+n,1,g[i][j]);
		}
	} 
	cout<<EK(0)<<endl;
	tot=1;	memset(head,0,sizeof head);
	for(int i=1;i<=n;i++)	add(s,i,1,0),add(i+n,t,1,0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			add(i,j+n,1,g[i][j]);
		}
	} 
	cout<<EK(1)<<endl;
	return 0;
}