记录编号	97023	评测结果	AAAAATAAATAA
题目名称	[USACO Feb05] 神秘的挤奶机	最终得分	83
用户昵称	Chenyao2333	是否通过	未通过
代码语言	C++	运行时间	4.310 s
提交时间	2014-04-16 13:33:08	内存使用	1.24 MiB

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>

const int MAXN=200+10;
const int MAXM=40000+10;
const int INF=10000*10000;

using namespace std;
int N,M,T;

int pos_len[MAXM]={0};//长度 从大到小排 
int len_tot=0;

struct edge{
	int from, to, cost;
	int cap,flow;
	bool operator < (const edge b) const {
		return cost<b.cost;
	}
}inputs[MAXM];

void read(){
	scanf("%d %d %d",&N,&M,&T);
	for(int i=0;i<M;i++){
		int f,t,c;scanf("%d %d %d",&f,&t,&c);
		inputs[i]=(edge){f,t,c,0,0}; 
	}
}

void get_len(){
	sort(inputs,inputs+M);
	int last_len=-1;
	for(int i=M-1;i>=0;i--){
		edge & e=inputs[i];
		if(e.cost!=last_len){
			last_len=e.cost;
			pos_len[len_tot++]=e.cost;
		}
	}
}

struct min_cost_max_flow{
	int s,t,m;
	vector<edge> edges;
	vector<int> G[MAXN];
	
	void init(int s,int t){
		this->s=s;this->t=t;
		edges.clear();
		for(int i=0;i<MAXN;i++){
			G[i].clear();
		}
	}
	
	void add_edge(int from,int to,int cost,int cap){
		edges.push_back((edge){from,to,cost,cap,0});
		edges.push_back((edge){to,from,-cost,0,0});
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	
	int d[MAXN],p[MAXN];bool inq[MAXN];
	int max_flow(int & tot_cost){
		queue<int> q;
		for(int i=0;i<MAXN;i++)d[i]=INF;
		memset(p,0,sizeof(p));
		memset(inq,0,sizeof(inq));
		d[s]=0;q.push(s);inq[s]=true;
		while(!q.empty()){
			int u=q.front();q.pop();inq[u]=false;
			for(int i=0;i<G[u].size();i++){
				edge & e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]>max(e.cost,d[u])){
					d[e.to]=max(e.cost,d[u]);
					p[e.to]=G[u][i];
					if(!inq[e.to]){
						q.push(e.to);
					}
				}
			}
		}
		
		if(d[t]==INF)return 0;
		
		int x=p[t];
		int flow=INF;
		while(true){
			edge & e=edges[x];
			flow=min(flow,e.cap-e.flow);
			if(e.from==s)break;
			x=p[e.from];
		}
		
		tot_cost=d[t];
		x=p[t];
		while(true){
			edge & e=edges[x];
			edge & ee=edges[x^1];
			e.flow+=flow;
			ee.flow-=flow;
			if(e.from==s)break;
			x=p[e.from];
		}
		return flow;
	}
	
	int min_cost(){
		int flow=0,cost=0;
		int f=0,c=0;
		while(f=max_flow(c)){
			flow+=f;
			cost=max(c,cost);
		}
		return cost;
	}
	void test(){
		for(int i=0;i<m;i++){
			edge & e=edges[i];
			printf("from:%d to%d cost:%d cap:%d flow:%d\n",e.from,e.to,e.cost,e.cap,e.flow); 
		}
		printf("========\n");
	}
}solver;

bool work(){
	solver.init(0,N);
	solver.add_edge(0,1,0,T);
	for(int i=0;i<M;i++){
		edge & e=inputs[i];
		solver.add_edge(e.from,e.to,e.cost,1);
		solver.add_edge(e.to,e.from,e.cost,1);
	}
	int min_cost=solver.min_cost();
	printf("%d\n",min_cost);
}

int main(){
	//freopen("in.txt","r",stdin);
	freopen("secretmilking.in","r",stdin);
	freopen("secretmilking.out","w",stdout);
	read();
	work();
	return 0;
}