bzoj1854 [Scoi2010]游戏 二分图匹配 并查集

Description

---

lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次？

对于30%的数据，保证N < =1000
对于100%的数据，保证N < =1000000

Solution

---

原来去年做过的单杀lyk可以这样做（不太记得了）
如果没有相差为1和从1开始的限制，直接连(ai,i)和(bi,i)求二分图最大匹配。容易发现顺序无关，只要不同即可
具体到这题可以考虑从1开始枚举看是否能找到对应点
有一个trick就是在匈牙利dfs的时候不需要每次清空vis数组，直接用时间戳标记会快很多

另一种做法参考自黄学长，对于一个武器看成一条边(a,b)
若一个连通块有n个点n-1条边（一棵树）则一定有一个点不能被取到
若一个连通块有n个点至少n条边，则任意一个点都能被取到
显然我们让一个连通块中最大的点不能被取是最优的。合并的时候记录一下，求答案的时候扫一遍即可

但是这样做是有问题的，即一个有自环的点连在了树上（画图脑补一下）的时候会错，那么离线所有的武器然后强行把ab相同的武器排在后面

Code

---

匈牙利做法

#include <stdio.h>
#include <string.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))
#define max(x,y) ((x)>(y)?(x):(y))
const int N=1000005;
const int E=2000005;
struct edge{int y,next;}e[E];
int link[N],ls[N],edCnt=0;
int vis[N];
int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}
void addEdge(int x,int y) {e[++edCnt]=(edge){y,ls[x]}; ls[x]=edCnt;}
int find(int now,int id) {
    for (int i=ls[now];i;i=e[i].next) {
        if (vis[e[i].y]==id) continue;
        vis[e[i].y]=id;
        if (!link[e[i].y]||find(link[e[i].y],id)) {
            link[e[i].y]=now;
            return 1;
        }
    }
    return 0;
}
int main(void) {
    freopen("data.in","r",stdin);
    freopen("std.out","w",stdout);
    int n=read(),mx=0;
    rep(i,1,n) {
        int x=read(),y=read();
        mx=max(mx,x); mx=max(mx,y);
        addEdge(x,i);
        addEdge(y,i);
    }
    int ans=0;
    rep(i,1,mx) {
        if (find(i,i)) ans++;
        else break;
    }
    printf("%d\n", ans);
    return 0;
}

并查集做法

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))
#define max(x,y) ((x)>(y)?(x):(y))
using std:: swap;
const int N=1000005;
int rank[N],fa[N],vis[N],x[N],y[N];
int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}
int get_father(int now) {return (!fa[now])?(now):(fa[now]=get_father(fa[now]));}
void merge(int x,int y) {
    x=get_father(x); y=get_father(y);
    if (x>y) swap(x,y); vis[x]=1;
    if (x!=y) fa[x]=y;
}
bool cmp(int a,int b) {return x[a]!=y[a]&&x[b]==y[b];}
int main(void) {
    int n=read(),mx=0;
    rep(i,1,n) {
        x[i]=read(),y[i]=read();
        rank[i]=i;
    }
    std:: sort(rank+1,rank+n+1,cmp);
    rep(ti,1,n) {
        int i=rank[ti];
        mx=max(mx,x[i]); mx=max(mx,y[i]);
        merge(x[i],y[i]);
    }
    int ans;
    rep(i,1,mx+1) if (!vis[i]) {
        ans=i-1;
        break;
    }
    printf("%d\n", ans);
}