自动搬运

查看原文

来自洛谷，原作者为

	wsy_jim 我把一路走来破碎的都装成箱 奇妙的是 送给你的那刻 缝中 开始有光了

搬运于2025-08-24 21:49:50，当前版本为作者最后更新于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;
}