题解 CF1240F 【Football】
Purple_wzy
·
·
题解
英文题面
题意：有一张n点m边的无向图，有k种颜色，你需要对每条边染上这k种颜色的其中一种，也可以不染色。需要满足以下限制:
设s_{i,j}表示以i为一端的边有多少个被染了颜色j。则\forall i,max_{j=1}^k s_{i,j}-min_{j=1}^k s_{i,j} \leq 2。
每个点有一个权值w_i，每染一条(i,j)的边，就会产生w_i +w_j的贡献。请输出一种合法染色方案，使得总贡献最大。
题解：首先，一定存在一种染色方案，使得所有边都被染色。
我们先考虑一下$k=2$的情况如何进行染色。考虑到如果所有节点的度数都为偶数，我们一定能够找到一条遍历了所有边的回路。因此我们可以试图将原图转化。
- 新建一个虚拟节点“0”；
- 对于存在度数为奇数的点的连通块，我们让所有这些点与0号节点连边；
- 对于所有点度数都为偶数的连通块，我们任意指定一个点，与0号节点连两条边。
不难发现这样构造之后，所有点的度数都是偶数。这样，我们就DFS找到这条回路，然后按照$1212\cdots 12$对边进行染色即可，最后将0号节点和与其有关的边删掉就行了。不难发现这样操作过后，每个点的$max-min \leq 1$。
那么对于$k>2$的情况，我们可以先将所有边随机染色，然后不断判断每个点的染色情况是否合法。如果有不合法的，就拿出$max$和$min$对应的这两种颜色，将图中这些边重新染色即可。可以发现这样操作并不会使任何点的$max-min$增加。
**（下面引用了大神Um_nik的复杂度证明。）**
我们设$P(Coloring)= \sum_i \sum_j s_{i,j}^2 $（$s_{i,j}$的定义见题目描述）。那么有$0 \leq P(Coloring) \leq 2nm$。每做一次操作，$P(Coloring)$是严格递减的。因此，操作次数的上界是$2nm$次，一次操作的复杂度是$O(n+m)$，那么总复杂度就是$O(nm(n+m))$。
但由于我们对所有边进行了随机化染色，因此，对于一个度数为$d$的节点，它对$P$的期望贡献是$d+d(d-1)/k=d^2/k+d(1-\frac{1}{k})$，可以近似看作是$d^2/k$。因此，期望操作次数是$O(m)$级别的，可以通过本题。
代码：
```c++
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
template<class D>I read(D &res){
res=0;register D g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const int INF=1e9+7;
typedef pair<int,int>pii;
vector<pii>e[110];
struct E{
int to,nt,id;
}t[20200];
#define T t[k].to
int n,m,k,x,clr,tot,v[110],vis[1010],head[110],du[110],a[1010],b[1010],c[1010],cnt[1010];
stack<int>s;
I add(int x,int y,int id){
t[++tot].to=y;t[tot].nt=head[x];head[x]=tot;t[tot].id=id;du[y]++;
}
I D_1(int x){
v[x]=1;
for(re k=head[x];k!=-1;k=t[k].nt){
if(!v[T])D_1(T);
}
}
I D_2(int x,int id){
for(re &k=head[x];k!=-1;k=t[k].nt){
if(!vis[k>>1]){
vis[k>>1]=1;
D_2(T,t[k].id);
}
}
s.emplace(id);
}
I recolor(int A,int B){
C(head,-1);tot=-1;C(v,0);C(du,0);
F(i,1,m)if(c[i]==A||c[i]==B)add(a[i],b[i],i),add(b[i],a[i],i);
F(i,1,n){
if(du[i]&1){
add(i,0,0);add(0,i,0);
if(!v[i])D_1(i);
}
}
F(i,1,n){
if(v[i]||(du[i]&1))continue;
D_1(i);
add(0,i,0);add(i,0,0);
add(0,i,0);add(i,0,0);
}
F(i,0,tot>>1)vis[i]=0;
D_2(0,0);clr=0;
while(!s.empty())c[s.top()]=(clr?A:B),s.pop(),clr^=1;
}
int main(){
srand((unsigned)time(0)+19260817);
read(n);read(m);read(k);
F(i,1,n)read(x);
F(i,1,m)read(a[i]),read(b[i]),e[a[i]].emplace_back(make_pair(b[i],i)),e[b[i]].emplace_back(make_pair(a[i],i)),c[i]=rand()%k+1;
while(1){
// cout<<"!";
re sn=1,mx,mn,px,pn;
F(i,1,n){
mx=0;px=pn=1;mn=INF;F(j,1,k)cnt[j]=0;
for(auto d:e[i])cnt[c[d.second]]++;
F(j,1,k){
if(cnt[j]>mx)mx=cnt[j],px=j;
if(cnt[j]<mn)mn=cnt[j],pn=j;
}
if(mx-mn>2)recolor(px,pn),sn=0;
}
if(sn)break;
}
F(i,1,m)printf("%d\n",c[i]);
return 0;
}
```