bzoj 1854

看起来像裸的二分图最大匹配，但是网上看来有神奇的并查集做法。

二分图最大匹配的匈牙利算法，这个网上有很多资料，就不说了。

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define maxd 10001
#define maxn 1000001
using namespace std;
int read(){
    char c; while(!isdigit(c=getchar())); int x=c-'0';
    while(isdigit(c=getchar())) x=x*10+c-'0'; return x;
}
vector<int> e[maxd];
int vis[maxn],cos[maxn];
bool find(int now,int tme){
    for(int i=0;i<e[now].size();i+=1)
        if(vis[e[now][i]]!=tme){
            vis[e[now][i]]=tme;
            if(!cos[e[now][i]] || find(cos[e[now][i]],tme))
                return cos[e[now][i]]=now,1;
        }
    return 0;
}
int main(){
    int n=read();
    for(int i=1;i<=n;i+=1){
        int x=read(),y=read();
        e[x].push_back(i);
        e[y].push_back(i);
    }
    for(int i=1;i<=maxd;i+=1)
        if(!find(i,i)) return printf("%d",i-1),0;
}

接下来是优美的并查集做法。大家可以去看看黄学长的博客。

如果出现一个装备两个属性值在同一集合，那么这个集合里所有的属性值都可以选择了，于是把这个集合的根标记为可以选择。

如果出现一个装备两个属性值在不同集合，如果两个集合的根中属性值小的未选择，就选择属性值小的，否则选择属性值大的。

#include<cstdio>
#include<cctype>
#include<algorithm>
#define maxd 10001
using namespace std;
int read(){
    char c; while(!isdigit(c=getchar())); int x=c-'0';
    while(isdigit(c=getchar())) x=x*10+c-'0'; return x;
}
int fa[maxd];
bool yes[maxd];
int find(int x){
    return x==fa[x]? x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    if(x>y) swap(x,y);
    if(!yes[x]) yes[x]=1; else yes[y]=1;
    fa[x]=y;
}
int main(){
    int n=read();
    for(int i=1;i<maxd;i+=1) fa[i]=i;
    while(n--){
        int x=find(read()),y=find(read());
        if(x!=y) merge(x,y); else yes[x]=1;
    }
    for(int i=1;i<=maxd;i+=1)
        if(!yes[i]) return printf("%d",i-1),0;
}