记录编号	300581	评测结果	AAAAAAAAAAAA
题目名称	[USACO Feb05] 神秘的挤奶机	最终得分	100
用户昵称	mildark	是否通过	通过
代码语言	C++	运行时间	1.138 s
提交时间	2016-08-28 18:50:43	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cassert>
using namespace std;
const int INF=0x7fffffff/2;
const int SIZEN=210;
class Edge{
public:
	int from,to,cap,flow,cost;
};
vector<Edge> edges;
vector<int> c[SIZEN];
void addedge(int from,int to,int cap,int cost){
	edges.push_back((Edge){from,to,cap,0,cost});
	edges.push_back((Edge){to,from,cap,0,cost});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
int N,S,T;
int f[SIZEN],father[SIZEN];
int ansflow=0,anscost=0;
bool Prim_one(int S){
	static bool used[SIZEN];
	for(int i=0;i<=N;i++) f[i]=INF;
	memset(used,0,sizeof(used));
	f[S]=0;
	while(true){
		int x=-1;
		for(int i=0;i<=N;i++){
			if(used[i]) continue;
			if(x==-1||f[i]<f[x]) x=i;
		}
		if(x==-1) break;
		used[x]=true;
		for(int i=0;i<c[x].size();i++){
			Edge &e=edges[c[x][i]];
			if(e.cap<=e.flow) continue;
			if(used[e.to]) continue;
			int now;
			if(e.flow==0) now=max(f[x],e.cost);
			else if(e.flow<0) now=f[x];
			if(now<f[e.to]){
				f[e.to]=now;
				father[e.to]=c[x][i];
			}
		}
	}
	if(!used[T]) return false;
	ansflow++;
	anscost=max(anscost,f[T]);
	int x=T;
	while(x!=S){
		int now=father[x];
		edges[now].flow++;
		edges[now^1].flow--;
		x=edges[now].from;
	}
	return true;
}
int MCMF(int mustflow){
	ansflow=anscost=0;
	for(int i=1;i<=mustflow;i++){
		assert(Prim_one(S));
	}
	return anscost;
}
int n,m,rides;
void makegraph(void){
	scanf("%d%d%d",&n,&m,&rides);
	N=n;S=1;T=N;
	int a,b,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&w);
		addedge(a,b,1,w);
	}
}
int main(){
	freopen("secretmilking.in","r",stdin);
	freopen("secretmilking.out","w",stdout);
	makegraph();
	printf("%d\n",MCMF(rides));
	return 0;
}