Topcoder Single Round Match 640 Div 1 T1 ChristmasTreeDecoration 题解

给你 N 个节点和一些边,每个点有个颜色,现在要你从这些边里选出 N-1 条构成一棵树,并且要让尽量少的边连接相同颜色的点

颜色以 vector <int> col 给出,col[i] 表示的是 i+1 节点的颜色(因为节点从 1 开始编号,而 vector 从 0 开始)。边以 vector <int> x,y 给出。

  • N will be between 2 and 50, inclusive.
  • The number of elements in col will be N exactly.
  • The number of elements in x will be between 1 and 200, inclusive.
  • The number of elements in y will be the same as the number of elements in x.
  • All elements of x and y will be between 1 and N, inclusive.
  • For each i, the numbers x[i] and y[i] will be different.
  • All unordered pairs (x[i], y[i]) will be distinct.
  • There will be at least one way to choose N-1 ribbons that form a connected graph.
  • Time limit (s): 2.000
  • Memory limit (MB): 256


Christmas is just around the corner, and Alice just decorated her Christmas tree. There are N stars on the tree. The stars are numbered 1 through N. Additionally, each star has some color. You are given the colors of stars as a vector col with N elements. For each i, col[i] is the color of star i+1. (Different integers represent different colors.)

Alice has prepared N-1 ribbons and she is now going to attach them to the tree. Each ribbon will connect two of the stars. The ribbons have to be placed in such a way that all stars and ribbons will hold together. (In other words, in the resulting arrangement the stars and ribbons will correspond to vertices and edges of a tree.)

Only some pairs of stars can be connected by a ribbon. You are given a list of all such pairs of stars in two vector s: x and y. For each valid i, it is possible to add a ribbon that connects the stars with numbers x[i] and y[i].

According to Alice, a ribbon that connects two stars that share the same color is less beautiful than a ribbon that connects two stars with different colors. Therefore, she would like to minimize the number of ribbons that connect two same-colored stars. Compute and return the smallest possible number of such ribbons.

典型的最小生成树,相同颜色边权为 1,不同颜色边权为 0,跑一趟 Kruscal 即可。


#include <bits/stdc++.h>
#define CLEAR(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn=55,maxm=205;
int n,m,fa[maxn],ans;

template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } 
template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; }

class ChristmasTreeDecoration {
    int solve( vector <int> col, vector <int> x, vector <int> y ) ;

struct EdgeInfo{
    int x,y,w;
inline bool cmp(EdgeInfo aa,EdgeInfo bb){
    return aa.w<bb.w;

inline void init(){
inline int getfa(int x){
    if (fa[x]==x) return x;
    return fa[x];
inline void Kruskal(){
    for (int i=0;i<m;i++){
        int fx=getfa(a[i].x),fy=getfa(a[i].y);
        if (fx==fy) continue;
int ChristmasTreeDecoration::solve(vector <int> col, vector <int> x, vector <int> y) {
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=0;i<m;i++) a[i].x=x[i],a[i].y=y[i],a[i].w=col[x[i]-1]==col[y[i]-1];
    return ans;