比赛 |
20110730 |
评测结果 |
AAAAAAAAAA |
题目名称 |
朦胧之旅 |
最终得分 |
100 |
用户昵称 |
PurpleShadow |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-30 08:51:08 |
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=5010,M=5010;
struct edge
{int adv,next;};
edge es[M];
int n,m,s;
int g[N],e;
inline void addedge(int a,int b)
{
es[++e].adv=b;
es[e].next=g[a];
g[a]=e;
}
void init()
{
scanf("%d%d%d",&n,&m,&s);
memset(g,0,sizeof(g));e=0;
int a,b,c;
while (s--)
{
scanf("%d%d%d",&a,&b,&c);
addedge(a,b);
}
}
int mx[N],my[N],dx[N],dy[N],q[N];
bool bfs()
{
memset(dx,0,sizeof(dx));
memset(dy,0,sizeof(dy));
int h=0,r=0,i,j,v;
for (i=1;i<=n;++i)
if (!mx[i]) q[++r]=i;
bool find=0;
while (h<r)
{
i=q[++h];
for (j=g[i];j;j=es[j].next)
if (!dy[v=es[j].adv])
{
dy[v]=dx[i]+1;
if (!my[v]) find=1;else
{
dx[my[v]]=dy[v]+1;
q[++r]=my[v];
}
}
}
return find;
}
bool dfs(int u)
{
int v,j;
for (j=g[u];j;j=es[j].next)
if (dy[v=es[j].adv]==dx[u]+1)
{
dy[v]=0;
if (!my[v]||dfs(my[v]))
{
my[v]=u;
mx[u]=v;
return 1;
}
}
return 0;
}
void slove()
{
memset(mx,0,sizeof(mx));
memset(my,0,sizeof(my));
int ans=0;
while (bfs())
for (int i=1;i<=n;++i)
if (!mx[i]&&dfs(i)) ++ans;
printf("0 %d\n",n-ans);
}
int main()
{
freopen("lovetravel.in","r",stdin);
freopen("lovetravel.out","w",stdout);
init();
slove();
return 0;
}