分配问题

套路费用流

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;const int S=0,T=100003,inf=0x3f3f3f3f;
int m,n,tmd;
int g[105][105],ecnt=1,head[1000005],from[1000005],dis[1000005];
bool inq[10005];
struct Edge {
	int to,nxt,val,cost,from;
} e[1000010];
void add(int bg,int ed,int val,int cost) {
	e[++ecnt].cost=cost;
	e[ecnt].from=bg;
	e[ecnt].nxt=head[bg];
	e[ecnt].to=ed;
	e[ecnt].val=val;
	head[bg]=ecnt;
}
void insert(int bg,int ed,int val,int cost) {
	add(bg,ed,val,cost);
	add(ed,bg,0,-cost);
}
queue<int>q;
bool spfa() {
	q.push(S);
	std::memset(dis,0x3f,sizeof dis);
	std::memset(inq,0,sizeof inq);
	dis[S]=0;
	inq[S]=1;
	while(!q.empty()) {
//		puts("!!!");
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=head[u],v; i; i=e[i].nxt) {
			v=e[i].to;
			if(dis[v]>dis[u]+e[i].cost&&e[i].val) {
				dis[v]=dis[u]+e[i].cost;
				from[v]=i;
				if(!inq[v]) q.push(v),inq[v]=1;
			}
		}
	}
	return dis[T]!=inf;
}
void min(int &x,int y) {x=x<y?x:y;}
int mincost,maxcost;
void mcf() {
	int x=inf,i=from[T];
	while(i) {min(x,e[i].val);i=from[e[i].from];}
	i=from[T];
	while(i) {
		e[i].val-=x;
		e[i^1].val+=x;
		mincost+=x*e[i].cost;
		i=from[e[i].from];
	}
}
//int g[105][105]; 
int main(){
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++) {
		insert(S,i,1,0);insert(i+n,T,1,0);
		for(int j=1;j<=n;j++) {
			scanf("%d",&x);g[i][j]=x;
			insert(i,j+n,1,x);
		}
	}
	while(spfa())mcf();
	cout<<mincost<<endl;
	memset(head,0,sizeof head);ecnt=1;
	for(int i=1,x;i<=n;i++) {
		insert(S,i,1,0);insert(i+n,T,1,0);
		for(int j=1;j<=n;j++) {
			insert(i,j+n,1,-g[i][j]);
		}
	}
	mincost=0;
	while(spfa())mcf();
	cout<<-mincost;
}