记录编号	338890	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] 晨跑	最终得分	100
用户昵称	面对疾风吧 疾风 疾风吧	是否通过	通过
代码语言	C++	运行时间	0.700 s
提交时间	2016-11-05 16:26:13	内存使用	1.66 MiB

#include<queue>
#include<deque>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 510
#define maxe 80010
#define INF (0x7f7f7f7f)
using namespace  std;
struct Edge{
	int f,t,next,flow,cost;
}e[maxe];int len=-1,head[maxn];
int n,m,ans,tans,dis[maxn],cnt[maxn],pre[maxn],spend,s,t;
bool inq[maxn];
void Addedge(int x,int y,int flow,int cost){
	//printf("x=%d y=%d flow=%d cost=%d\n",x,y,flow,cost);
	len++;
	e[len].t=y;
	e[len].f=x;
	e[len].flow=flow;
	e[len].cost=cost;
	e[len].next=head[x];
	head[x]=len;
}
bool Spfa(){
	memset(dis,0x7f,sizeof dis);
	memset(cnt,0,sizeof cnt);
	memset(pre,0,sizeof pre);
	memset(inq,0,sizeof inq);
	deque<int> q;
	q.push_back(1);
	inq[1]=1;
	dis[1]=0;
	cnt[1]++;
	while(!q.empty()){
		int x=q.front();q.pop_front();
		inq[x]=0;
		//printf("x=%d\n",x);
		for(int i=head[x];i!=-1;i=e[i].next){
			int y=e[i].t;
			if(dis[y]>dis[x]+e[i].cost&&e[i].flow>0){
				//printf("y=%d\n",y);
				dis[y]=dis[x]+e[i].cost;
				pre[y]=i;
				if(!inq[y]){
					inq[y]=1;
					cnt[y]++;
					if(!q.empty()&&dis[y]<dis[q.front()]) q.push_front(y);
					else q.push_back(y);
				}
			}
		}
	}
	if(cnt[n]>0)return 1;
	return 0;
}
int Find(int x,int low){
	if(x==1)return low;
	int p=pre[x];
	int f=Find(e[p].f,min(low,e[p].flow));
	e[p].flow-=f;
	e[p^1].flow+=f;
	return f;
}
void Karp(){
	while(Spfa()){
		tans=Find(n,INF);
		ans+=tans;
		spend+=tans*dis[n];
	}
}
int main(){
	freopen("run.in","r",stdin);freopen("run.out","w",stdout);
	
	memset(head,-1,sizeof head);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		if(x==1&&y==n) Addedge(x,y,1,z),Addedge(y,x,0,-z);
		else{
			if(x==1) Addedge(x,y,1,z),Addedge(y,x,0,-z);
			else{
				if(y==1) Addedge(x+n,y,1,z),Addedge(y,x+n,0,-z);
				else Addedge(x+n,y,1,z),Addedge(y,x+n,0,-z);
			}
		}
	}
	for(int i=2;i<n;i++) Addedge(i,i+n,1,0),Addedge(i+n,i,0,0);
	Karp();
	printf("%d %d\n",ans,spend);
	
	getchar();getchar();
	fclose(stdin);fclose(stdout);
	return 0;
}