记录编号 27460 评测结果 AAAAAAAAAA
题目名称 朦胧之旅 最终得分 100
用户昵称 Gravatardonny 是否通过 通过
代码语言 C++ 运行时间 0.269 s
提交时间 2011-09-23 19:14:14 内存使用 24.23 MiB
显示代码纯文本
#include <iostream>
#include <fstream>

using namespace std;

int i,j,k,l,n,m,s;
bool a[5010][5010],v[5010],t[5010];
int total;
int flag[5010];

bool dfs(int x)
{
	int i;
	for (i=1;i<=n;i++)
	{
		if ((a[x][i])and(!v[i]))
		{
			v[i]=1;
			if ((flag[i]==0)or(dfs(flag[i])))
			{
				flag[i]=x;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	ifstream fin("lovetravel.in");
	ofstream fout("lovetravel.out");
	
	fin>>n>>m>>s;
	
	for (i=1;i<=n;i++)
		t[i]=false;
	for (i=1;i<=s;i++)
	{
		fin>>j>>k>>l;
		a[j][k]=true;
		t[j]=true;
	}
	
	total=0;
	for (i=1;i<=n;i++)
	{
		if (t[i])
		{
			for (j=1;j<=n;j++)
				v[j]=0;
			if (dfs(i))
				total++;
		}
	}
	
	fout<<"0 "<<n-total<<endl;
	
	fin.close();
	fout.close();
	
	return 0;
}