每日总结-1月15日

acm 图论

2021ACM寒假集训

发布日期: 2022-01-15

文章字数: 903

图论进阶

网络流

最大流
最小费用流

今日战况

Standing

前言

今天主要就是把 MCMF(最小费用最大流) 给理解了，不过还不够熟练，自己写应该还是写不出板子。

部分题目

B题: 分配问题

题目传送门

题目

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

输入格式

文件的第 1 行有 1 个正整数 n ，表示有 n 件工作要分配给 n 个人做。

接下来的 n 行中，每行有 n 个整数 c_ij ，表示第 i 个人做第 j 件工作产生的效益为 c_ij 。

输出格式

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

样例

Input
1
2
3
4
5
6
5
2 2 2 1 2
2 3 1 2 4
2 0 1 1 1
2 3 4 3 3
3 2 1 2 1
Output
1
2
5
14
数据范围与提示

1 <= n <= 100

思路

可构建一个二分图，一边是人，一边是工作，用一遍 MCMF(最小费用最大流)可求出最小总效益，之后，把所有边都删掉，再重新建一个图，里面的 cost 全部变为原来的负数，再用一遍 MCMF 可求出最大总效益的相反数。

代码

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#define Inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int MAXX=205;
const double eps=0.0000001;

struct rode{
	int st,en,flow,cap,cost;
};
vector<rode> ro;
vector<int> to[MAXX];
int n,m;
int cur[MAXX],d[MAXX],guanxi[MAXX][MAXX],a[MAXX],p[MAXX];
bool vis[MAXX],inq[MAXX];

inline void add(int st,int en,int cap,int cost){
	rode re;int si=ro.size();
	re.st=st;re.en=en;re.flow=0;re.cap=cap;re.cost=cost;
	ro.push_back(re);to[st].push_back(si);
	re.st=en;re.en=st;re.flow=0;re.cap=0;re.cost=-cost;
	ro.push_back(re);to[en].push_back(si+1);
}

bool bfss(int st,int en,int& flow,LL& cost){
	for(int i=st;i<=en;++i){
		d[i]=Inf;
		inq[i]=0;
	}
	queue<int> qq;qq.push(st);
	d[st]=0;inq[st]=true;p[st]=0;a[st]=Inf;
	
	while(!qq.empty()){
		int jj=qq.front();qq.pop();
		inq[jj]=false;
		int si=to[jj].size();
		for(int i=0;i<si;++i){
			rode& kk=ro[to[jj][i]];
			if(kk.cap>kk.flow&&d[kk.en]>d[jj]+kk.cost){
				d[kk.en]=d[jj]+kk.cost;
				p[kk.en]=to[jj][i];
				a[kk.en]=min(a[jj],kk.cap-kk.flow);
				if(!inq[kk.en]){
					qq.push(kk.en);
					inq[kk.en]=true;
				}
			}
		}
	}
	if(d[en]==Inf) return false;
	cost+=(LL)d[en]*(LL)a[en];
	flow+=a[en];
	int jj=en;
	while(jj!=st){
		ro[p[jj]].flow+=a[en];
		ro[p[jj]^1].flow-=a[en];
		jj=ro[p[jj]].st;
	}
	return true;
}

int mcmf(int st,int en,LL& cost){
	int flow=0;cost=0;
	while(bfss(st,en,flow,cost));
	return flow;
}

void solve_it(){
	scanf("%d",&n);
	int n1=2*n+1;
	LL minans,maxans;
	int ff;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			scanf("%d",&guanxi[i][j]);
			add(i,n+j,1,guanxi[i][j]);
		}
	for(int i=1;i<=n;++i){
		add(0,i,1,0);
		add(i+n,n1,1,0);
	}
	ff=mcmf(0,n1,minans);
	printf("%lld\n",minans);
	
	ro.clear();
	for(int i=0;i<=n1;++i)
		to[i].clear();
	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			add(i,n+j,1,-guanxi[i][j]);
		}
	for(int i=1;i<=n;++i){
		add(0,i,1,0);
		add(i+n,n1,1,0);
	}
	ff=mcmf(0,n1,maxans);
	printf("%lld\n",-maxans);
}

int main(){
//	int t;scanf("%d",&t);
//	while(t--)
		solve_it();
	
	return 0;
}