【2018百度之星资格赛】F 三原色图

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6349

Knowledge Point: 最小生成树算法Prim&Kruskal

Summarize:

　　本题采用构造两颗带权最小生成树的方法求解；

　　求解最小生成树的方法有prim和kruskal两种方法，但是网上题解皆采用的后者；

　　我用prim写了之后发现AC不了，主要是prim采用的邻接矩阵的方法存储边对这道题不适用，题目没有说过没有重复的边，而邻接矩阵会覆盖掉上一条颜色相同的边；

　　此外需注意：

　　　　1. 点数为1时特判；

　　　　2. 当边数小于点数减一的时候可以直接判断无解；

　　　　3. 当两棵树最小权值相同或都有解时，需分别记录两个最小值，并分别与当时剩下的边相加，每次都需比较之后再输出两者之间的最小值。

附kruskal代码，先按边从小到大排序后再依次求解：

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define INF 1e9

 const int N = 1e5+;

 const int M = 5e5+;

 int n,m;

 struct Edge {

     int from, to, value;

     bool operator<(const Edge &a) {

         return value<a.value;

     }

 }edge[M];

 int vis[N], f[N];

 int find(int x)

 {

     if(x != f[x])

         f[x] = find(f[x]);

     return f[x];

 }

 void init()

 {

     for(int i=; i<n; i++)

         vis[i]=, f[i] = i;

     sort(edge, edge+m);

 }

 void kruskal()

 {

     int cost=;

     for(int i=; i<m; i++) {

         int x = find(edge[i].from);

         int y = find(edge[i].to);

         if(x != y) {

             f[x] = y;

             cost += edge[i].value;

             vis[edge[i].from] = vis[edge[i].to] = ;

         }

     }

     cout<<cost<<endl;

 }

 int main()

 {

     cin>>n>>m;

     for(int i=; i<m; i++)

         cin>>edge[i].from>>edge[i].to>>edge[i].value;

     init();

     kruskal();

     return ;

 }

巴特西

【2018百度之星资格赛】F 三原色图 - 最小生成树

最新文章

热门文章