正文
bzoj 1854: [Scoi2010]游戏
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
#include<cstdio>
#include<iostream>
#include<cstring>
#define M 2000008
using namespace std;
int pi[M],n,m,f[M],i,head[M],next[M],u[M],cnt,tim;
bool xun(int a1)
{
for(int j=head[a1];j;j=next[j])
if(f[u[j]]!=tim)
{
f[u[j]]=tim;
if(!pi[u[j]]||xun(pi[u[j]]))
{
pi[u[j]]=a1;
return ;
}
}
return ;
}
void jia(int a1,int a2)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
u[cnt]=a2;
return;
}
int main()
{
scanf("%d",&n);
for( i=;i<=n;i++)
{
int a1,a2;
scanf("%d%d",&a1,&a2);
jia(a1,i);
jia(a2,i);
}
for( i=;i<=;i++)
{
tim++;
if(!xun(i))
break;
}
printf("%d\n",i-);
}
属性与序号建边 跑二分图匹配。