Topcoder Single Round Match 640 Div 1 T1 ChristmasTreeDecoration 题解

• 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.

#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 {
public:
int solve( vector <int> col, vector <int> x, vector <int> y ) ;
};

struct EdgeInfo{
int x,y,w;
}a[maxm];
inline bool cmp(EdgeInfo aa,EdgeInfo bb){
return aa.w<bb.w;
}

inline void init(){
CLEAR(a);ans=0;
}
inline int getfa(int x){
if (fa[x]==x) return x;
fa[x]=getfa(fa[x]);
return fa[x];
}
inline void Kruskal(){
sort(a,a+m,cmp);
for (int i=0;i<m;i++){
int fx=getfa(a[i].x),fy=getfa(a[i].y);
if (fx==fy) continue;
ans+=a[i].w;fa[fx]=fy;
}
}
int ChristmasTreeDecoration::solve(vector <int> col, vector <int> x, vector <int> y) {
init();
n=col.size();m=x.size();
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];
Kruskal();
return ans;
}