BZOJ3060: [Poi2012]Tour de Byteotia

题解:

首先如果对于一条边的两个端点均满足$>k$,则显然可以缩到一起变成一个点.

然后对于剩下的边,我们需要添加若干条使得不出现环,因为如果出现了环肯定有$\leq{k}$的点在环上.

我们可以按任意顺序添加,因为最后图的形态是固定的.

所以直接并查集水过就可以.

代码(非常蠢):

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 1000010
#define M 2000010
struct Edge{
    int a,b;
    Edge(){}
    Edge(int _a,int _b):a(_a),b(_b){
        if(a>b)
            swap(a,b);
    }
    bool operator<(const Edge&B)const{
        return a>B.a;
    }
}E[M];
 
inline int getc(){
    static const int L=1<<15;
    static char buf[L],*S=buf,*T=buf;
    if(S==T){
        T=(S=buf)+fread(buf,1,L,stdin);
        if(S==T)
            return EOF;
    }
    return*S++;
}
inline int getint(){
    int c;
    while(!isdigit(c=getc()));
    int x=c-'0';
    while(isdigit(c=getc()))
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
 
int r[N],siz[N];
inline int find(int x){
    int q=x,rq;
    for(;x!=r[x];x=r[x]);
    for(;q!=x;rq=r[q],r[q]=x,q=rq);
    return x;
}
inline void merge(int a,int b){
    if(siz[a]>siz[b])
        swap(a,b);
    siz[b]+=siz[a];
    r[a]=b;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n,m,k,i;
    n=getint();
    m=getint();
    k=getint();
    for(i=1;i<=m;++i)
        E[i]=Edge(getint(),getint());
    for(i=1;i<=n;++i)
        r[i]=i,siz[i]=1;
    int ra,rb,cnt=0;
    for(i=1;i<=m;++i){
        if(E[i].b<=k){
            ra=find(E[i].a);
            rb=find(E[i].b);
            if(ra!=rb)
                ++cnt,merge(ra,rb);
        }
    }
    for(i=1;i<=m;++i){
        if(E[i].a>k){
            ra=find(E[i].a);
            rb=find(E[i].b);
            ++cnt;
            if(ra!=rb)
                merge(ra,rb);
        }
    }
    for(i=1;i<=m;++i){
        if(E[i].a<=k&&E[i].b>k){
            ra=find(E[i].a);
            rb=find(E[i].b);
            if(ra!=rb)
                ++cnt,merge(ra,rb);
        }
    }
    cout<<m-cnt<<endl;
    return 0;
}