Topcoder SRM 640 Div1 T1 ChristmasTreeDecoration 题解

/ 0评 /

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

知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/tc-640-div1-t1/


发表评论

电子邮件地址不会被公开。 必填项已用*标注