【Codeforces 212A】Privatization / 题解

【Codeforces 212A】Privatization / 题解

Description

Berland 和 Beerland 之间有发达的航班网络,它们都属于 Berland 国营公司 BerAvia。每条航线将 Berland 的一个城市和 Beerland 的一个城市连接起来。

最近,Berland 决定私有化 BerAvia,他们将航线卖给了 $k$ 家私人公司。这些公司希望航线的划分尽量均匀。

具体地,对每个城市 $i$,定义不均匀度

$$w_i=\max_j a_{i,j}-\min_j a_{i,j}$$

其中,$a_{i,j}$ 代表公司 $j$ 拥有的经过 $i$ 市的航线数量。

Berland 政府希望不均匀度的平均值最小,请帮助它们找到最佳方案,并输出不均匀度的和。

Idea

这道题可以跑网络流但是我不会。

我们将每个城市拆分成数目最少的点,使得每个点的度数 $\leq k$。对于新图,做二分图最小边染色即可,可以证明二分图最小边染色数 $=\max \text{Degree}$。具体地,我们利用一个类似匈牙利的算法实现。

设 $f_{i,j}$ 代表新图上从 $x$ 点出发,颜色为 $j$ 的边另一个端点的编号。每次新加入一条从 $x$ 到 $y$ 的边时,找到这两个端点可以使用的最小颜色编号,分别设为 $cx,cy$。如果 $cx=cy$,可以直接加边;否则,我们要为 $y$ 端点处占用了 $cx$ 的边更换颜色。具体地,我们可以找到一条从 $y$ 出发的,颜色为 $cx,cy$ 交替出现的增广路,将这条增广路上的 $cx,cy$ 互换。

这样做的时间复杂度为 $\Theta(\frac{m^2}{k}+mn)$。

Code

#include <bits/stdc++.h>
#define maxn 310
#define maxm 90010
using namespace std;
int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
    return x;
}
int nA,nB,m,k,ans,x,y,c1,c2,cnt;
int deg[maxn<<1],be[maxm],w[maxn],w2[maxn];
int id[10005][maxn],f[10005][maxn];
void rv(int x,int c1,int c2){
    swap(f[x][c1],f[x][c2]);
    swap(id[x][c1],id[x][c2]);
    be[id[x][c2]]=c2;
    if (f[x][c2]) rv(f[x][c2],c2,c1);
}
int main(){
    nA=read(),nB=read(),m=read(),k=read();
    for (int i=1;i<=m;++i){
        x=read(),y=read();
        if (deg[x]%k==0) w[x]=++cnt;
        if (deg[nA+y]%k==0) w2[y]=++cnt;
        deg[x]++,deg[nA+y]++;
        x=w[x],y=w2[y];
        c1=0,c2=0;
        for (int j=1;j<=k;++j)
            if (!f[x][j]) {c1=j;break;}
        for (int j=1;j<=k;++j)
            if (!f[y][j]) {c2=j;break;}
        if (f[y][c1]) rv(y,c1,c2);
        f[x][c1]=y;id[x][c1]=i;
        f[y][c1]=x;id[y][c1]=i;
        be[i]=c1;
    }
    for (int i=1;i<=nA+nB;++i)
        ans+=(bool)(deg[i]%k);
    printf("%d\n",ans);
    for (int i=1;i<=m;++i)
        printf("%d ",be[i]);
    putchar('\n');
    return 0;
}
Show Comments