记录编号 |
27460 |
评测结果 |
AAAAAAAAAA |
题目名称 |
朦胧之旅 |
最终得分 |
100 |
用户昵称 |
donny |
是否通过 |
通过 |
代码语言 |
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;
}