自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 22:41:06，当前版本为作者最后更新于2025-04-04 21:57:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如题，这是一道假题。

实践得出贪心是假的，所以应该只有 $O(n^n)$ 的爆搜做法有正确性，然而剪枝能过全靠逆天数据。

听说复杂度已经高上天，常数就卡了一遍又一遍（？

既然不愿意写搜索，那么不妨写一个乱搞做法（笑）

我们充分发扬人类智慧：

将所有人全部赋上一个权值，然后按权值排序。

根据数学直觉，在此时跑一个贪心后，答案距离正解肯定不会离得太远。

所以我们只需要多随机赋几次权值来计算答案。

这样速度快得飞起，在 $n=100$ 时都可以在 1s 内卡过。

#include<bits/stdc++.h>
using namespace std;
vector<int>ve[105];
int a[105];
int ans;
int ret=1e9;
void dfs(int x){
    bitset<105>bi;
    bi.set();
    bi[0]=0;
    for(int i=0;i<ve[x].size();i++)
        bi[a[ve[x][i]]]=0;
    a[x]=bi._Find_first();
    ans=max(ans,a[x]);
}
struct fish{
    int x,id;
}flc[105];
bool cmp(fish l,fish r){
    return l.x<r.x;
}
int main(){
    srand(time(0));
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)flc[i].id=i;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    for(int r=1;r<=n;r++){
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++)flc[i].x=rand();
        sort(flc+1,flc+1+n,cmp);
        for(int i=1;i<=n;i++)dfs(flc[i].id);
        ret=min(ans,ret);
        ans=0;
    }
    cout<<ret;
    return 0;
}

这能过实在是太好笑了，有没有人来卡一下啊。