CF720C Homework
构造题，先每行都涂满直至逼近答案，然后对于剩下几层暴搜。
然而换了翻译之后 (sum{n*m} leq 10^5)，而且加上联通的限制吗，貌似直接暴搜也能跑过了，只是慢一些。
总结一下：构造题不要想直接构造出答案，先用一部分达到逼近答案的效果，剩下的部分就可以比较容易地准确获得答案。
CF600F Edge coloring of bipartite graph
根据大胆猜测小心求证，有一个结论：二分图最小颜色数等于最大度数。
具体操作上，参考匈牙利算法，对于 (u,v) 的连边，如果 (mex(u)!=mex(v))，就先强行让这条边染上 (mex(u))，然后再找到原来连 (mex(u)) 的边，让它连 (mex(v))，以此类推，直到不能再找为止。由于二分图的性质，可以证明一定能重新配对出一个合法的方案。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 2021,M = 1e5+10;
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
int a,b,m;
int u[M],v[M];
int col[N<<1][N];
int ind[N<<1];
signed main()
{
a=read(),b=read(),m=read();
for(int i=1;i<=m;i++)
{
u[i]=read(),v[i]=read()+a;
ind[v[i]]++,ind[u[i]]++;
}
int ans=0;
for(int i=1;i<=2000;i++) ans=max(ans,ind[i]);
for(int i=1;i<=m;i++)
{
int x=1,y=1;
while(col[u[i]][x]) x++;
while(col[v[i]][y]) y++;
col[u[i]][x]=v[i],col[v[i]][y]=u[i];
if(x==y) continue;
int now=u[i],w=x;
while(now)
{
swap(col[now][x],col[now][y]);
now=col[now][w];
w^=(x^y);
}
}
printf("%d
",ans);
for(int i=1;i<=m;i++)
for(int j=1;j<=ans;j++)
if(col[u[i]][j]==v[i])
printf("%d ",j);
return 0;
}