题解：P8653 [蓝桥杯 2017 国 C] 分考场(假题：最小色数)

· · 题解

如题，这是一道假题。

实践得出贪心是假的，所以应该只有 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;
}

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