NC14254 Color（二分图匹配）

我们贪心的猜测肯定是每次用二分图匹配，这样答案就是最小的

这基本上对的，因此可以每次都可以消除最多的边并且满足不会遇到同一个点

但是有一个纰漏，我们首先知道最小值肯定是度数最大的点的度数，因为这个点的每个出边都不同，并且我们每次只能减少一条边。

因此我们每次按照目前的度数排序去重复做匈牙利算法，因为如果我们随便找一个点去，这样可能虽然是最大匹配，但是没有匹配到度数最大的那个点，因此他的边数没有减少

所以答案还要大。

而我们每次按度数排序做，就会发现，度数最大的点的边都会减少1（可能不止一个），那么做完全部次就能把所有点的边数减完

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N=2e5+200;
const int mod=1e9+7;
int match[N];
int from[N],to[N],st[N];
vector<int> g[N];
int color[2010][2010];
int d[N],id[N];
bool cmp(int a,int b){
    return d[a]>d[b];
}
bool find(int x){
    int i;
    for(i=0;i<g[x].size();i++){
        int j=g[x][i];
        if(!st[j]){
            st[j]=1;
            if(match[j]==0||find(match[j])){
                match[j]=x;
                match[x]=j;
                return true;
            }
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    int i,j;
    int mx=0;
    for(i=1;i<=m;i++){
        cin>>from[i]>>to[i];
        d[from[i]]++,d[to[i]]++;
    }
    for(i=1;i<=n;i++){
        mx=max(mx,d[i]);
    }
    for(i=1;i<=mx;i++){
        for(j=1;j<=n;j++)
            g[j].clear();
        for(j=1;j<=m;j++){
            if(!color[from[j]][to[j]]){
                g[from[j]].push_back(to[j]);
                g[to[j]].push_back(from[j]);
            }
        }
        for(j=1;j<=n;j++){
            id[j]=j;
            match[j]=0;
        }
        sort(id+1,id+1+n,cmp);
        for(int j=1,p=id[j];j<=n;j++,p=id[j]){
            if(!match[p]){
                for(int k=1;k<=n;k++){
                    st[k]=0;
                }
                find(p);
            }
        }
        for(j=1;j<=n;j++){
            if(match[j]){
                color[j][match[j]]=i;
                d[j]--;
            }
        }
    }
    cout<<mx<<endl;
    for(i=1;i<=m;i++){
        cout<<color[from[i]][to[i]]<<endl;
    }
    return 0;
}