记录编号	218438	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] 晨跑	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.343 s
提交时间	2016-01-09 19:07:36	内存使用	5.55 MiB

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
const int inf=0x7fffffff/2-1; 
int n,m,tot=1,h[maxn];
struct edge{
	int to,next,cap,flow,w;
}G[maxn*30];
int S,T,pre[maxn];
bool vis[maxn];
int dis[maxn];

void add(int x,int y,int cap,int z){
	++tot; G[tot].to=y; G[tot].cap=cap;
	G[tot].w=z; G[tot].next=h[x]; h[x]=tot;
	++tot; G[tot].to=x; G[tot].cap=0;
	G[tot].w=-z; G[tot].next=h[y]; h[y]=tot;
	G[tot].flow=0; G[tot-1].flow=0;
}

bool spfa(){
	for (int i=S;i<=T*2;++i){vis[i]=0;dis[i]=inf;pre[i]=-1;}
	vis[S]=1; dis[S]=0; deque<int>q ;q.push_front(S);
	while (!q.empty()){
		int u=q.front(); q.pop_front(); vis[u]=0;
		for (int i=h[u];i;i=G[i].next){
			int v=G[i].to;
			if (dis[v]>dis[u]+G[i].w&&G[i].cap>G[i].flow){
				dis[v]=dis[u]+G[i].w;
				pre[v]=i;
				if (!vis[v]){
					vis[v]=1; 
					if (!q.empty()&&dis[v]<dis[q.front()]) q.push_front(v);
					else q.push_back(v);
				}
			}
		}
	}return pre[T]!=-1;
}

void min_cost_flow(){
	int ans=0,flow=0;
	while (spfa()){
		int Flow=inf;
		for (int i=pre[T];i!=-1;i=pre[G[i^1].to])
		    Flow=min(Flow,G[i].cap-G[i].flow);
		for (int i=pre[T];i!=-1;i=pre[G[i^1].to]){
			G[i].flow+=Flow; G[i^1].flow-=Flow;
			ans+=G[i].w*Flow;
		}flow+=Flow;
	}printf("%d %d",flow,ans);
}

int main(){
	freopen("run.in","r",stdin);
	freopen("run.out","w",stdout);
	scanf("%d%d",&n,&m);
	S=1; T=n;
	for (int i=1;i<=m;++i){
		int x,y,z; 
		scanf("%d%d%d",&x,&y,&z);
		if (x!=1&&x!=n) x+=n;
		add(x,y,1,z);
	}
	for (int i=2;i<n;++i)
	    add(i,i+n,1,0);
	min_cost_flow();
}