[USACO4.4]追查坏牛奶

题目描述
你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

输入格式
第一行: 两个整数N(2<=N<=32)、M(0<=M<=1000), N表示仓库的数目，M表示运输卡车的数量。仓库1代 表发货工厂，仓库N代表有三聚氰胺的牛奶要发往的零售商。 第2…M+1行: 每行3个整数Si,Ei,Ci。其中Si,Ei表示这 辆卡车的出发仓库，目的仓库。Ci(0 <= C i <= 2,000,000) 表示让这辆卡车停止运输的损失。

输出格式
两个整数C、T：C表示最小的损失，T表示在损失最小的前提下，最少要停止的卡车数。

输入输出样例
输入 #1复制
4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

输出 #1复制
60 1

说明/提示
题目翻译来自NOCOW。

USACO Training Section 4.4

第一个就是简单的最小割，学过网络流都知道。

第二问求对应的最小边数，我们对边集体加一个很大的权值即可。就能保证在相同最小割时，边数最小。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=40,M=1e5+10;
int n,m,h[N],s,t,val=1e12,res,cnt;
int head[N],nex[M],to[M],w[M],tot=1;
inline void ade(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){ade(a,b,c); ade(b,a,0);}
inline int bfs(){
	queue<int> q;	q.push(s);	memset(h,0,sizeof h); h[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi,w[i^1]+=mi,fl+=mi,f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
signed main(){
	cin>>n>>m; t=n; s=1;
	for(int i=1,a,b,c;i<=m;i++)	cin>>a>>b>>c,add(a,b,c+val);
	while(bfs())	res+=dfs(s,inf);
	while(res>val)	res-=val,cnt++;
	cout<<res<<' '<<cnt<<endl;
	return 0;
}