记录编号	338752	评测结果	AAAAAAAAAA
题目名称	[SGU U252]铁路网	最终得分	100
用户昵称	面对疾风吧 疾风 疾风吧	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2016-11-05 15:10:50	内存使用	1.11 MiB

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

1 5
-----
5 8
2 3 10
5 4 2
1 3 7
4 1 1
5 2 3
5 1 2
2 1 2
4 2 1

1 12
*/