记录编号	87597	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] 晨跑	最终得分	100
用户昵称	雪狼	是否通过	通过
代码语言	C++	运行时间	0.355 s
提交时间	2014-02-05 22:08:33	内存使用	0.29 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<iostream>
#define maxn 400+10
#define INF ~0U>>2
using namespace std;

struct edge{
	int from,to,cap,flow,cost;
};

struct MCML{
	int n,m,s,t;
	vector<edge>E;
	vector<int>G[maxn];
	bool vis[maxn];
	int d[maxn];
	int p[maxn];
	int a[maxn];
	
	
	void init(int n){
		this->n=n;
		for(int i=0;i<=n;i++)G[i].clear();
		E.clear();
	}
	
	void addedge(int from,int to,int cap,int cost){
		E.push_back((edge){from,to,cap,0,cost});
		E.push_back((edge){to,from,0,0,-cost});
		int s=E.size();
		G[from].push_back(s-2);
		G[to].push_back(s-1);
	}
	
	bool SPFA(int s,int t,int& cost){
		for(int i=0;i<=n;i++)d[i]=INF;
		memset(vis,0,sizeof(vis));
		d[s]=0,vis[s]=1,p[s]=0,a[s]=INF;
		
		queue<int>Q;
		Q.push(s);
		while(!Q.empty()){
			int x=Q.front();Q.pop();
			vis[x]=0;
			for(int i=0;i<G[x].size();i++){
				edge& e=E[G[x][i]];
				edge& ee=E[G[x][i]^1];
				if(e.cap>e.flow&&d[e.to]>d[e.from]+e.cost){
					d[e.to]=d[e.from]+e.cost;
					p[e.to]=G[x][i];
					a[e.to]=min(a[e.from],e.cap-e.flow);
					if(!vis[e.to]){Q.push(e.to);vis[e.to]=1;}
				}
			}
		}
		if(d[t]==INF)return 0;
		cost+=d[t]*a[t];
		int u=t;
		while(u!=s){
			E[p[u]].flow+=a[t];
			E[p[u]^1].flow-=a[t];
			u=E[p[u]].from;
		}
		return 1;
	}
	
	int Mincost(int s,int t){
		int cost=0,sum=0;
		while(SPFA(s,t,cost))sum++;
		printf("%d %d\n",sum,cost);
	}
}D;

int in(int s){return s*2;}
int out(int s){return s*2+1;}

void setIO(string s){
	string in=s+".in",out=s+".out";
	freopen(in.c_str(),"r",stdin);
	freopen(out.c_str(),"w",stdout);
}

int main(){
	setIO("run");
	
	int n,m,s,t;
	int a,b,c;
	scanf("%d%d",&n,&m);
	D.init(n*2);
	for(int i=1;i<=n;i++)D.addedge(in(i),out(i),1,0);
	while(m--){
		scanf("%d%d%d",&a,&b,&c);
		D.addedge(out(a),in(b),1,c);
	}
	D.Mincost(out(1),in(n));
	return 0;
}