[网络流24题]分配问题

题目：洛谷P4014、codevs1915。

题目大意：
有 ( n ) 件工作要分配给 ( n ) 个人做。第 ( i ) 个人做第 ( j ) 件工作产生的效益为 ( c_{ij} )。求最大总效益和最小总效益（每人只能生产一个零件）。
解题思路：
二分图带权最大/最小匹配。跑费用流即可。
求最大值则费用取负跑，最小值则直接跑，建两遍图跑即可。

C++ Code：

#include<bits/stdc++.h>
using namespace std;
#define T 300
int n;
struct Graph{
	std::queue<int>q;
	int head[305],cnt,pre_e[305],a[305],d[305];
	bool vis[305];
	struct edge{
		int from,to,cap,cost,nxt;
	}e[40005];
	inline void addedge(const int u,const int v,const int flow,const int cost){
		e[++cnt]=(edge){u,v,flow,cost,head[u]};
		head[u]=cnt;
		e[++cnt]=(edge){v,u,0,-cost,head[v]};
		head[v]=cnt;
	}
	Graph():cnt(1){
		memset(head,-1,sizeof head);
	}
	bool bfs(int& flow,int& cost){
		memset(d,0x3f,sizeof d);
		memset(a,0x3f,sizeof a);
		memset(vis,0,sizeof vis);
		memset(pre_e,0,sizeof pre_e);
		d[0]=0;
		vis[0]=1;
		q.push(0);
		while(!q.empty()){
			int u=q.front();q.pop();
			vis[u]=0;
			for(int i=head[u];~i;i=e[i].nxt)
			if(e[i].cap&&d[e[i].to]>d[u]+e[i].cost){
				d[e[i].to]=d[u]+e[i].cost;
				a[e[i].to]=min(a[u],e[i].cap);
				pre_e[e[i].to]=i;
				if(!vis[e[i].to]){
					vis[e[i].to]=1;
					q.push(e[i].to);
				}
			}
		}
		if(d[T]==0x3f3f3f3f)return 0;
		flow+=a[T];
		cost+=d[T]*a[T];
		for(int i=T;i;i=e[pre_e[i]].from){
			e[pre_e[i]].cap-=a[T];
			e[pre_e[i]^1].cap+=a[T];
		}
		return 1;
	}
	int ek(){
		int flow=0,cost=0;
		while(bfs(flow,cost));
		return cost;
	}
}g1,g2;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j){
		int p;
		cin>>p;
		g1.addedge(i,n+j,1,p);
		g2.addedge(i,n+j,1,-p);
	}
	for(int i=1;i<=n;++i)
	g1.addedge(0,i,1,0),g2.addedge(0,i,1,0),
	g1.addedge(n+i,T,1,0),g2.addedge(n+i,T,1,0);
	cout<<g1.ek()<<'
'<<-g2.ek()<<'
';
	return 0;
}