题意

https://vjudge.net/problem/CodeForces-1244D

有一棵树，有3种颜色，第i个节点染成第j种颜色的代价是c(i,j)，现在要你求出一种染色方案，使得总代价最小，且对于任意三个相邻的节点，颜色不能相同。输出最小代价与其中一种方案。无解输出-1。

思路

首先可以发现当一个点的度数为3，那么它连的三个点的颜色必须互不相同，这样就把三种三色用完了，这个点就染不了了，于是如果存在度大于等于3的点，那么无解。

那么有解的树可以伸直成一条链，我们暴力枚举任意相邻的三个点的颜色，有3！种，然后我们暴力dfs从这三点的两端向外延伸即可。

复杂度O（6*n）

代码

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=1e5+5;

const int mod=1e9+7;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

ll c[4][N];

ll du[N],col[N],rec[N];

vector<int>g[N];

int flag=0,s,a,b;

void dfs(int u,int fa)

{

    int sz=g[u].size();

    for(int i=0; i<sz; i++)

    {

        int v=g[u][i];

        if(v==fa)

            continue;

        for(int i=1; i<=3; i++)

        {

            if(col[fa]!=i&&col[u]!=i)

            {

                col[v]=i;

                break;

            }

        }

        dfs(v,u);

    }

}

int main()

{

    std::ios::sync_with_stdio(false);

    int n;

    cin>>n;

    for(int i=1; i<=3; i++)

    {

        for(int j=1; j<=n; j++)

        {

            cin>>c[i][j];

        }

    }

    for(int i=0; i<n-1; i++)

    {

        int u,v;

        cin>>u>>v;

        g[u].push_back(v);

        g[v].push_back(u);

        du[u]++,du[v]++;

        if(du[u]==2)

        {

            s=u;

        }

        if(du[v]==2)

            s=v;

        if(du[u]>=3||du[v]>=3)

        {

            flag=1;

        }

    }

    if(flag)

    {

        cout<<-1<<endl;

        return 0;

    }

    a=g[s][0],b=g[s][1];

    ll ans=1e16;

    for(int i=1; i<=3; i++)

    {

        for(int j=1; j<=3; j++)

        {

            for(int k=1; k<=3; k++)

            {

                if(i==j||j==k||i==k) continue;

                for(int i=1; i<=n; i++)

                    col[i]=0;

                col[s]=i,col[a]=j,col[b]=k;

                dfs(a,s);

                dfs(b,s);

                ll sum=0;

                for(int i=1; i<=n; i++)

                {

                    sum+=c[col[i]][i];

                }

                if(sum<ans)

                {

                    ans=sum;

                    for(int i=1; i<=n; i++)

                        rec[i]=col[i];

                }

            }

        }

    }

    cout<<ans<<endl;

    for(int i=1; i<=n; i++)

        cout<<rec[i]<<" ";

    cout<<endl;

    return 0;

}

巴特西

CodeForces - 1244D （思维+暴力）

题意

思路

代码

最新文章

热门文章