Topcoder SRM 640 Div1 T1 ChristmasTreeDecoration 题解

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 {
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;
}