?

題目傳送門

題意：如何花最小的代價使得一棵樹劃分開且不含同類節點

分析：當一條邊連接的左右集合同類點小于等于1，那么不用刪除，將兩個集合合并，要求最小代價，那么貪心思想將權值降序排序，刪除后剩下的就是最小值了。樹形DP的方法以后再補上

收獲：進一步理解Kruskal的算法過程，碰到新的問題要往經典的算法模型上轉換

?

代碼：

/************************************************ * Author :Running_Time * Created Time :2015-8-24 10:48:20 * File Name :D.cpp************************************************/#include <cstdio> #include <algorithm> #include <iostream> #include <sstream> #include <cstring> #include <cmath> #include <string> #include <vector> #include <queue> #include <deque> #include <stack> #include <list> #include <map> #include <set> #include <bitset> #include <cstdlib> #include <ctime> using namespace std;#define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 typedef long long ll; const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; struct UF {int rt[N], rk[N];void init(void) {memset (rt, -1, sizeof (rt));memset (rk, 0, sizeof (rk));}int Find(int x) {return rt[x] == -1 ? x : rt[x] = Find (rt[x]);}void Union(int x, int y) {x = Find (x), y = Find (y);if (x == y) return ;if (rk[x] >= rk[y]) {rt[y] = x; rk[x] += rk[y];}else {rt[x] = y; rk[y] += rk[x];}}bool same(int x, int y) {return (Find (x) == Find (y));} }uf; struct Edge {int u, v, w;bool operator < (const Edge &r) const {return w > r.w;} }; int n, k; vector<Edge> G;int main(void) {int T; scanf ("%d", &T);while (T--) {scanf ("%d%d", &n, &k);uf.init (); G.clear ();ll ans = 0;for (int u, v, w, i=1; i<n; ++i) {scanf ("%d%d%d", &u, &v, &w); ans += w;G.push_back ((Edge) {u, v, w});}sort (G.begin (), G.end ());for (int x, i=0; i<k; ++i) {scanf ("%d", &x); uf.rk[x] = 1;}for (int i=0; i<n-1; ++i) {int u = G[i].u, v = G[i].v, w = G[i].w;u = uf.Find (u); v = uf.Find (v);if (uf.rk[u] + uf.rk[v] <= 1) {ans -= w; uf.Union (u, v);}}printf ("%I64d\n", ans);}return 0; }

　　

轉載于:https://www.cnblogs.com/Running-Time/p/4755054.html

總結

以上是生活随笔為你收集整理的Kruskal HDOJ 4313 Matrix的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。