记录编号	26975	评测结果	AAAAAAAAAA
题目名称	朦胧之旅	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2011-07-30 14:55:46	内存使用	1.91 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>

using namespace std;
int n,m,S,T,pn;
int d[10001],vd[10001];
bool y[5001];

struct edge
{
	int t,c;
	edge *next,*op;
}E[100001],*V[10001];
int eh;
inline void addedge(int a,int b,int c)
{
	E[++eh].next=V[a];  V[a]=E+eh;  V[a]->t=b;  V[a]->c=c;
	E[++eh].next=V[b];  V[b]=E+eh;  V[b]->t=a;  V[b]->c=0;
	V[a]->op=V[b];  V[b]->op=V[a];
}
void init()
{
	int s=0,a,b,c;S=0;T=10000;
	d[S]=3;
	scanf("%d%d%d",&n,&m,&s);
	for (;s;--s)
	{
		scanf("%d%d%d",&a,&b,&c);
		if (!y[a]) {d[a]=2;vd[2]++;addedge(S,a,1);}
		if (!y[b]) {d[b]=1;vd[1]++;addedge(b,T,1);}
		y[a]=y[b]=true;
		if (c!=0) addedge(a,b,1);
	}
}

int dfs(int u,int flow)
{
	if (u==T) return flow;
	int now=0;
	for (edge *e=V[u];e;e=e->next)
	if (e->c && d[e->t]+1==d[u])
	{
		int t=dfs(e->t,min(e->c,flow-now));
		if (t)
		{
			e->c -= t;
			e->op->c += t;
			now += t;
			if (flow==now) return now;
		}
	}
	if (d[S]>=pn) return now;
	if (--vd[d[u]]==0) d[S]=pn;
	vd[++d[u]]++;
	return now;
}

void solve()
{
	int flow=n;pn=n+2;
	vd[0]=vd[3]=1;
	while (d[S]<pn)
	{
		flow-=dfs(S,flow);
	}
	printf("0 %d\n",flow);
}

int main()
{
	freopen("lovetravel.in","r",stdin);
	freopen("lovetravel.out","w",stdout);
	init();
	solve();
	return 0;
}