codeforces 1141G Privatization of Roads in Treeland

佚名 5年前 (2019-03-26) 算法 1048人围观抢沙发百度已收录

题目链接：http://codeforces.com/contest/1141/problem/G

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题目大意：

给你一个无向连通图。每条边都有颜色，如果存在一个点的临边中有超过两条边颜色相同，这个点就不好。你要用最少的颜色涂完所有的边，保证不好的点不超过k。

反正吧，我没想过cfG题会这么水。不过过的人还真挺少的。（QaQ，比赛没看这题被F2空间卡崩了）

思路：

先离线处理下。

先记录所有点的度，然后大到小排序。找到度第k+1大的度。

这个度就是答案。

因为我可以认为大于答案的度的点都是不好的；

我们怎么找到这些点呢？

dfs遍历。

对于不好的点直接全部画1就好了。

#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define MAX 200010
#define fi first
#define se second

map< pair<int,int> ,int>ans;
pair<int,int> x[MAX];
vector <int> y[MAX];
int z[MAX];
bool k[MAX];

bool cmp(const int a,const int b)
{
    return a>b;
}
int Ans;
void dfs(int r,int b)
{
    if(k[r])
    {
        return;
    }
    k[r]=true;

    int len=y[r].size();

    if(len>Ans)
    {
        for(int i=0; i<len; i++)
        {
            if(k[y[r][i]])continue;
            ans[make_pair(r,y[r][i])]=1;
            ans[make_pair(y[r][i],r)]=1;
            dfs(y[r][i],1);
        }
    }
    else{
        bool kk=false;
        int cer=0;
        for(int i=0; i<len; i++)
        {
            if(k[y[r][i]])continue;
            cer++;
            if(cer==b){
                kk=true;
            }
            ans[make_pair(r,y[r][i])]=cer+kk;
            ans[make_pair(y[r][i],r)]=cer+kk;
            dfs(y[r][i],cer+kk);
        }
    }

}
signed main()
{
    ios::sync_with_stdio(false);

    int n,k;

    cin>>n>>k;

    for(int i=1; i<=n-1; i++)
    {
        cin>>x[i].fi>>x[i].se;
        z[x[i].fi]++;
        z[x[i].se]++;
        y[x[i].fi].push_back(x[i].se);
        y[x[i].se].push_back(x[i].fi);
    }

    sort(z+1,z+1+n,cmp);

    Ans=z[k+1];

    cout<<Ans<<endl;
    dfs(1,0);

    for(int i=1;i<n;i++){
        cout<<ans[x[i]]<<" ";
    }
    return 0;
}