https://www.luogu.org/problem/show?pid=1640
题目描述
lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次？
输入输出格式
输入格式：
输入的第一行是一个整数N，表示lxhgww拥有N种装备接下来N行，是对这N种装备的描述，每行2个数字，表示第i种装备的2个属性值
输出格式：
输出一行，包括1个数字，表示lxhgww最多能连续攻击的次数。
输入输出样例
输入样例#1：
3
1 2
3 2
4 5
输出样例#1：
2
说明
Limitation
对于30%的数据，保证N < =1000
对于100%的数据，保证N < =1000000
来源：SCOI 2010
并查集：
优先用每个装备较低的属性，数组记录是否可以攻击到的属性
find没有return 还对8个点、、
#include <cstdio> const int N();
int fa[N],n;
bool if_[N];
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
} inline void read(int &x)
{
x=; register char ch=getchar();
for(;ch>''||ch<'';) ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';
} int AC()
{
read(n); for(int i=;i<=n+;i++) fa[i]=i;
for(int fx,fy,x,y,i=;i<=n;i++)
{
read(x),read(y);
fx=find(x),fy=find(y);
if(fx==fy) if_[fx]=;
else
{
if(fx>fy) {int tmp=fx;fx=fy;fy=tmp;}
if_[fx]=;
fa[fx]=fy;
}
}
for(int i=;i<=n+;i++)
if(!if_[i])
{
printf("%d\n",i-);
return ;
}
return ;
} int Hope=AC();
int main(){;}
二分图：
属性向装备连边，求出最早没法匹配的属性。
#include <cstring>
#include <cstdio> const int N(+);
int n,head[N],sumedge;
struct Edge
{
int v,next;
Edge(int v=,int next=):v(v),next(next){}
}edge[N<<];
inline void ins(int u,int v)
{
edge[++sumedge]=Edge(v,head[u]);
head[u]=sumedge;
} int vis[N];
int match[N],sumvis;
bool find(int u)
{
for(int v,i=head[u];i;i=edge[i].next)
{
v=edge[i].v;
if(vis[v]==sumvis) continue;
vis[v]=sumvis;
if(!match[v]||find(match[v]))
{
match[v]=u;
return true;
}
}
return false;
} inline void read(int &x)
{
x=; register char ch=getchar();
for(;ch>''||ch<'';) ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';
} int AC()
{
read(n);
for(int u,v,i=;i<=n;i++)
{
read(u),read(v);
ins(u,i),ins(v,i);
}
int ans=;
for(int i=;i<=;i++)
{
sumvis++;
if(find(i)) ans++;
else break;
}
printf("%d\n",ans);
return ;
} int Hope=AC();
int main(){;}