P3524 [POI2011]IMP-Party 题解

wsy_jim · 2021-07-20 20:38:09 · 题解

0x01 题意

给定一张 3N 个点的图，保证其中有一个大小为 2N 的团，找到一个大小为 N 的团

0x02 解

每次选两个不连通的点，

根据题意这两个点最多有一个在团里，

那么我们每次删掉这两个不连通的点，

删去了 N 对之后，

最多有 N 个在团中的点被删掉，

最少有 N 个不在团里的点被删掉，

剩下点的必定都在团里

0x03 码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=0x3f3f3f3f,N=3010;

int n,m,mapp[N][N],vis[N],cnt=0;

inline int read(){
    int x=0,y=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*y;
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int a,b;
        a=read(),b=read();
        mapp[a][b]=mapp[b][a]=1;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        for(int j=i+1;j<=n;j++){
            if(mapp[i][j]||vis[j]) continue;
            vis[i]=vis[j]=1;
            break;
        }
    }
    for(int i=1;i<=n;i++) if(!vis[i]){
        printf("%d ",i);
        cnt++;
        if(cnt*3==n) return 0;
    }
    cout<<endl;
    return 0;
}