比赛 20110730 评测结果 AAAAAAAAAA
题目名称 朦胧之旅 最终得分 100
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-30 10:25:50
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=5222;
const int MAXM=22222;
const int oo=1000000;

struct edge
{
	int t,f;
	edge *p,*op;
}*v[MAXN],e[MAXM];

int n,m,i,j,k,s,ans=0,S,T,vd[MAXN],d[MAXN],es=-1;
bool b[MAXN];

inline void addedge(int i,int j)
{
	e[++es].t=j; e[es].f=1; e[es].p=v[i]; v[i]=e+es;
	e[++es].t=i; e[es].f=0; e[es].p=v[j]; v[j]=e+es;
	v[i]->op=v[j];
	v[j]->op=v[i];
}

int dfs(int u,int flow)
{
	int re=0,tmp;
	if (u==T) return flow;
	for (edge *x=v[u];x;x=x->p)
		if (x->f && d[u]==d[x->t]+1)
		{
			tmp=dfs(x->t,min(flow-re,x->f));
			x->f-=tmp;
			x->op->f+=tmp;
			re+=tmp;
			if (re==flow) return re;
		}
	--vd[d[u]];
	if (vd[d[u]]==0) d[S]=T+1;
	vd[++d[u]]++;
	return re;
}

int main()
{
	freopen("lovetravel.in","r",stdin);
	freopen("lovetravel.out","w",stdout);
	scanf("%d%d%d",&n,&m,&s);
	memset(b,false,sizeof(b));
	S=n+1;
	T=n+2;
	while (s--)
	{
		scanf("%d%d%d",&i,&j,&k);
		addedge(i,j);
		if (!b[i])
		{
			b[i]=true;
			addedge(S,i);
		}
		if (!b[j])
		{
			b[j]=true;
			addedge(j,T);
		}
	}
	memset(vd,0,sizeof(vd));
	memset(d,0,sizeof(d));
	vd[0]=T;
	while (d[S]<=T) ans+=dfs(S,oo);
	printf("0 %d\n",n-ans);
	return 0;
}