洛谷P1344 [USACO4.4]追查坏牛奶Pollutant Control 基础最小割模型

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题解

说实话这是一个水题……一眼看出来就是最小割模型……

我们只需要付出最小的代价破坏汽车(可以看作是道路)使得S和T不连通就行了。

于是我们连有向边,以损失为此边流量。建好图直接跑1到N的最小割就是了。这样最小损失就求出来了。

至于第二问,我们可以像第一问一样把边的流量改为1,然后再跑最小割。这是一定正确的,请自行证明。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = (num<<3) + (num<<1) + c - '0';
	return (flag ? -1 : 1) * num;
}
int S,T;
const int maxn = 55;
const int maxm = 1005;
const int INF = 1e9;
struct Flow{
	int h[maxn],cur[maxn];
	struct edge{
		int to,next,cap;
	}e[maxm<<1];
	int cnt;
	void add(int u,int v,int c){
		e[cnt].to = v;e[cnt].next = h[u];e[cnt].cap = c;
		h[u] = cnt++;
		return;
	}
	int d[maxn];
	bool BFS(int s,int t){
		queue<int>q;
		for(int i = s;i <= t;++i){
			d[i] = INF;
		}
		d[s] = 0;
		q.push(s);
		while(!q.empty()){
			int now = q.front();
			q.pop();
			for(int i = h[now];i != -1;i = e[i].next){
				int v = e[i].to;
				if(e[i].cap > 0 && d[v] == INF){
					d[v] = d[now] + 1;
					q.push(v);
				}
			}
		}
		return (d[t] != INF);
	}
	int DFS(int now,int t,int a){
		int flow = 0;
		int f;
		if(a == 0 || now == t)return a;
		for(int &i = cur[now];i != -1;i = e[i].next){
			int v = e[i].to;
			if(d[v] == d[now] + 1 && e[i].cap > 0){
				f = min(a - flow,e[i].cap);
				f = DFS(v,t,f);
				flow += f;
				e[i].cap -= f;
				e[i^1].cap += f;
				if(flow == a)break;
			}
		}
		return flow;
	}
	int dinic(int s,int t){
		int flow = 0;
		while(BFS(s,t)){
			for(int i = s;i <= t;++i)cur[i] = h[i];
			flow += DFS(s,t,INF);
		}
		return flow;
	}
	void init(){
		memset(h,-1,sizeof(h));
		cnt = 0;
		return;
	}
}ans1,ans2;
int n,m;
int s,e,c;
int main(){
	n = get_num();
	m = get_num();
	ans1.init();ans2.init();
	for(int i = 1;i <= m;++i){
		s = get_num();
		e = get_num();
		c = get_num();
		ans1.add(s,e,c);ans1.add(e,s,0);
		ans2.add(s,e,1);ans2.add(e,s,0);
	}
	printf("%d %d\n",ans1.dinic(1,n),ans2.dinic(1,n));
	return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00