Color

题目描述

给一个没有重边的二分图, 要求给边染色. 有公共点的边不能同色. 问最少用多少种颜色, 并任意构造一组方案.

输入描述:

第一行两个数n和m表示图的点数和边数(0<n<1001,0<m<2001).
之后m行每行2个数表示一条边的两个端点. 点从1编号到n.
保证给的是二分图.

输出描述:

第一行一个数k表示需要多少种颜***r>接下来m行每行一个数表示输入的边的颜色. 按照输入的顺序输出, 颜色从1编号到k.

题解

用公共点的边不同色，即从一个点出来的边颜色不同。二分图里有一个定理，二分图边着色所需最小颜色数，等于图中点的最大度数。
现在的问题就是我们怎样去构造染色方法。有公共点的边不能同色，那么如果我们每次找到的这条边，他的两个端点在这次查找中都没出现过的话，这样的一组边就可以用相同颜色来染色了。找到的边在这次查找中都没出现过，其实就相当于对二分图进行匹配。
所以我们多次调用匈牙利算法进行匹配，每次匹配出来的一组边染上相同的颜色即可。
但要注意的是我们每次匹配的时候要从最大度数的点进行匹配，否则可能度数小的点都把度数大的点所能匹配的点匹配了，那么这次过后对于度数大的点所需要的染色数量仍然没有改变，结果就不是最优的了。以上困惑了我好久，经过询问大佬才明白

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2010;
int used[N],nxt[N],color[N][N],l[N],r[N],degree[N],idx[N];
vector<int> v[N];
int n,m,ans;
bool  match(int x){
    for(auto k:v[x]){
        if(!used[k]){
            used[k]=1;
            if(nxt[k]==0||match(nxt[k])){
                nxt[k]=x;nxt[x]=k;
                return true;
            }
        }
    }
    return false;
}
////////////////////////////////////////////////////////////////////////
int main(){
    n=gn(),m=gn();
    repi(i,1,m){
        l[i]=gn(),r[i]=gn();
        ans=max(ans,++degree[l[i]]);
        ans=max(ans,++degree[r[i]]);
    }
    printf("%d\n",ans);
    repi(i,1,n)idx[i]=i;
    repi(i,1,ans){
        repi(j,1,m){
            if(!color[l[j]][r[j]]){
                v[l[j]].pb(r[j]);
                v[r[j]].pb(l[j]);
            }
        }
        repi(j,1,n){
            nxt[j]=0;
        }
        sort(idx+1,idx+1+n,[](int x,int y){
            return degree[x]>degree[y];
        });
        repi(j,1,n){
            if(!nxt[idx[j]]){
                memset(used,0,sizeof(used));
                match(idx[j]);
            }
        }
        repi(j,1,n){
            if(nxt[j]){
                color[j][nxt[j]]=i;
                --degree[j];
            }
            v[j].clear();
        }
    }
    repi(i,1,m){
        print(color[l[i]][r[i]]),putchar(10);
    }
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/