CTREE - Tô màu nhỏ nhất

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include "stdio.h"
#include "iostream"
#include "vector"

using namespace std;

#define maxc 30

int n;
vector<vector<int> > ke;
int f[10001][maxc+1];
int father[10001], la[10001];

void nhap() {
    int u,v;
    scanf("%d",&n);
    ke.resize(n+1);
    for(int i=1;i<n;++i) {
        scanf("%d%d",&u,&v);
        ke[u].push_back(v);
        ke[v].push_back(u);
    }    
}

void dfs(int i) {
    for(vector<int>::iterator p=ke[i].begin();p!=ke[i].end();++p)
        if(*p!=father[i]) {
            father[*p]=i;
            dfs(*p);
        }    
    for(int k=1;k<=maxc;++k) {
        f[i][k]=k;
        for(vector<int>::iterator p=ke[i].begin();p!=ke[i].end();++p) if(*p!=father[i]) {
            int fmin=1000000000;
            for(int t=1;t<=maxc;++t) if(t!=k) fmin<?=f[*p][t];
            f[i][k]+=fmin;
        }    
    }    
}    

void truyvet(int i,int k) {
    la[i]=k;
    for(vector<int>::iterator p=ke[i].begin();p!=ke[i].end();++p) if(*p!=father[i]) {
        int fmin=1000000000,tmin=-1;
        for(int t=1;t<=maxc;++t) if(t!=k && fmin>f[*p][t]) {
            fmin=f[*p][t];
            tmin=t;
        }    
        truyvet(*p,tmin);
    }    
}    

void xuly() {
    dfs(1);
    int fmin=1000000000,kmin=-1;
    for(int k=1;k<=maxc;++k) {
        if(f[1][k]<fmin) {
            fmin=f[1][k];
            kmin=k;
        }    
    }
    truyvet(1,kmin);
    printf("%d\n",f[1][kmin]);
    for(int i=1;i<=n;++i) printf("%d\n",la[i]);
}

int main() {
    nhap();
    xuly();
    return 0;
}
    

Download