记录编号	97012	评测结果	AAAAAAAAAAAA
题目名称	[USACO Feb05] 神秘的挤奶机	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.568 s
提交时间	2014-04-16 11:56:00	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=210,INF=0x7fffffff/2;
int N,M,T;
class EDGE{
public:
	int from,to,cap,flow,w;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
int ans=0,ansflow=0;
bool Prim_find(int S,int T){
	bool flag[SIZEN]={0};
	int f[SIZEN]={0};
	priority_queue<pair<int,int> > Q;
	int pre[SIZEN]={0};
	for(int i=1;i<=N;i++) f[i]=INF;
	f[S]=0;Q.push(make_pair(-f[S],S));
	while(!Q.empty()){
		int x=Q.top().second;Q.pop();
		if(flag[x]) continue;
		flag[x]=true;
		for(int i=0;i<c[x].size();i++){
			EDGE &e=edges[c[x][i]];
			if(e.cap<=e.flow) continue;
			if(flag[e.to]) continue;
			int now;
			if(e.flow==0) now=max(f[x],e.w);//加流
			else if(e.flow<0) now=f[x];//退流
			if(now<f[e.to]){
				f[e.to]=now;
				Q.push(make_pair(-f[e.to],e.to));
				pre[e.to]=c[x][i];
			}
		}
	}
	if(f[T]==INF) return false;
	int minf=INF,x;
	x=T;
	while(x!=S){
		EDGE &e=edges[pre[x]];
		minf=min(minf,e.cap-e.flow);
		x=e.from;
	}
	ansflow+=minf;
	ans=max(ans,f[T]);
	x=T;
	while(x!=S){
		edges[pre[x]].flow+=minf;
		edges[pre[x]^1].flow-=minf;
		x=edges[pre[x]].from;
	}
	return true;
}
void work(void){
	while(ansflow<T&&Prim_find(1,N));
	printf("%d\n",ans);
}
void addedge(int from,int to,int cap,int w){//这里添加了两条边
	edges.push_back((EDGE){from,to,cap,0,w});
	edges.push_back((EDGE){to,from,cap,0,w});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
void read(void){
	scanf("%d%d%d",&N,&M,&T);
	int a,b,L;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&a,&b,&L);
		addedge(a,b,1,L);
	}
}
int main(){
	freopen("secretmilking.in","r",stdin);
	freopen("secretmilking.out","w",stdout);
	read();
	work();
	return 0;
}