时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
Special Judge, 64bit IO Format: %lld
题目描述
给一个没有重边的二分图, 要求给边染色. 有公共点的边不能同色. 问最少用多少种颜色, 并任意构造一组方案. 输入描述:
第一行两个数n和m表示图的点数和边数(0<n<1001,0<m<2001). 之后m行每行2个数表示一条边的两个端点. 点从1编号到n.
保证给的是二分图.
输出描述:
第一行一个数k表示需要多少种颜色. 接下来m行每行一个数表示输入的边的颜色. 按照输入的顺序输出, 颜色从1编号到k.
示例1
输入
4 4
1 2
1 3
2 4
3 4
输出
2
1
2
2
1
题解：
题目要求有公共点的边不能同色，最后要求最少的颜色数
所以有公共点的边我们就让他同***r> 二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。（也就是匹配出没有共同点的边）
边数最大的子图就是最大匹配
所以我们可以多次调用二分图最大匹配（比如匈牙利算法），为每次匹配出来的边附上色，直到全部匹配
但是有的边可能在多次最大匹配中都可以被匹配上，怎么保证最优呢？
根据题意，每个点所连的边颜色各不相同，所以答案就是度数最大的那个点，所以每次匹配有限从度数大的开始匹配
具体为什么从最大度下手？可以从反证法，假设从最小度开始匹配会怎么样。也可以看看官方解释
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+9;
int d[maxn];//点i的度数
int x[maxn],y[maxn];
int id[maxn],col[1040][1040];
vector<int>g[maxn];
bool vis[maxn];
int match[maxn];
int n,m;
bool cmp(int x,int y)
{
return d[x]>d[y];
}
bool dfs(int u)
{
for(auto v:g[u])
{
if(!vis[v])
{
vis[v]=1;
if(match[v]==0||dfs(match[v]))
{
match[v]=u;
match[u]=v;
return 1;
}
}
}
return 0;
}
void init()
{
memset(match,0,sizeof(match));
sort(id+1,id+1+n,cmp);
}
int main()
{
cin>>n>>m;
int ans=0;
for(int i=1;i<=m;i++)
{
cin>>x[i]>>y[i];
d[x[i]]++;
d[y[i]]++;
ans=max(ans,max(d[x[i]],d[y[i]]));
}
for(int i=1;i<=n;i++)id[i]=i;
for(int i=1;i<=ans;i++)
{
for(int j=1;j<=m;j++)
if(!col[x[j]][y[j]])//该边还未被标记
{
g[x[j]].push_back(y[j]);//存边
g[y[j]].push_back(x[j]);
}
init();
for(int j=1,k=id[j];j<=n;j++,k=id[j])//从度数最大的开始下手
{
if(!match[k])
{
memset(vis,0,sizeof(vis));
dfs(k);
}
}
for(int j=1;j<=n;j++)//对每一次最大匹配进行染色
{
if(match[j])//如果j已经匹配
{
col[j][match[j]]=i;//染上色
d[j]--;
}
g[j].clear();
}
}
cout<<ans<<endl;
for(int i=1;i<=m;i++)
cout<<col[x[i]][y[i]]<<endl;
return 0;
}
京公网安备 11010502036488号