POJ3164 Command Network (最小树形图， 朱刘算法)

算法)"/>

POJ3164 Command Network (最小树形图， 朱刘算法)

题目大意

给定一个有 n n n个点的坐标和 m m m条边的有向图(从 1 1 1~ n n n编号, n < = 100 n <= 100 n<=100)， 边权为点之间的欧式距离， 选择一些边，让 1 1 1号点能到达其它任何一个点，求这些边的最小权值之和。

思路

若该图是一个无向图，那么这题就是求一颗最小生成树， 跑一边 P r i m Prim Prim 算法即可。但是这题是一张有向图，那么 P r i m Prim Prim算法就不可行了。这题其实就是求定根的最小树形图， 算法有两种， 一种是朱刘算法，时间复杂度 O ( n m ) O(nm) O(nm),另一种是tarjan大佬用栈 + 并查集 + 可合并堆优化的算法，时间复杂度 O ( m l o g n ) O(mlogn) O(mlogn)。这里我用的是朱刘算法，算法流程大概如下：

① 贪心的找除根节点以外的其余点的最小入边,如果图不连通那么无解， 否则把边的信息记录下来。
② 此时， 若找出来的边构成的图不含环， 那么这就是一个最小树形图， 结束算法。
③ 否则， 缩点， 由于环里的点只能有一条入边， 所以在当前最小入边构成的图中不可能有除环上以外的点进入环内， 由于我们要消除环， 所以一定要将环上的一条入边删除，在另一个不属于环内的点与该入边对应的点连一条边， 若该入边是 w p r e w_{pre} wpre​,新边是 w n x t w_{nxt} wnxt​, 那么进行了这一次操作后对答案的影响是 w n x t w_{nxt} wnxt​ − - − w p r e w_{pre} wpre​, 所以只要缩完点后向环连一条 w n x t w_{nxt} wnxt​ − - − w p r e w_{pre} wpre​的边即可,之后重复以上步骤。

由于入边不好找， 所以我建的反图， 在反图上找最小出边。由于每个点仅有一条出边， 因此找环缩点只需要dfs即可，我这里是把缩完点后的图存在一个新邻接表里， 然后复制给原来的邻接表。
如果是不定根的最小树形图， 其实可以建立一个超级源点， 与图中每个点都有一条边权极大的边， 然后就转换为定根的最小树形图了.

现在写一题要一整天， 越学感觉自己越菜，有点晕

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAX_N = 105, MAX_M = 1e4 + 5;
struct Point{int a, b;}p[MAX_N];
int n, m;
int h[MAX_N], ne[MAX_M], e[MAX_M], idx, id[MAX_N], cir[MAX_N], h1[MAX_N], ne1[MAX_M], e1[MAX_M], idx1;
double w1[MAX_M], w[MAX_M], ans;
bool vis[MAX_N], cur_vis[MAX_N], has_circle, del[MAX_N], on_circle[MAX_N];
void add(int a, int b, double c){e[++idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}
void add2(int a, int b, double c){e1[++idx1] = b, ne1[idx1] = h1[a], w1[idx1] = c, h1[a] = idx1;
}
double dist(int a, int b){return sqrt(1.0 * (p[a].a - p[b].a) * (p[a].a - p[b].a) + 1.0 * (p[a].b - p[b].b) * (p[a].b - p[b].b));
}
bool find_min(){for(int u = 2;u <= n; u++){if(del[u]) continue;double min_val = 1e11;for(int i = h[u];i;i = ne[i])if(w[i] < min_val) min_val = w[i], id[u] = i;if(min_val > 9e9) return false;}return true;
}
void dfs(int u){cur_vis[u] = 1;cir[u] = u;int nxt = e[id[u]];if(!cir[nxt]) dfs(nxt);else if(cur_vis[nxt]){for(int i = nxt;i != u;i = e[id[i]]) cir[i] = nxt, on_circle[i] = 1;cir[u] = nxt, on_circle[u] = 1;has_circle = 1;}cur_vis[u] = 0;
}
bool find_circle(){memset(cir, 0, sizeof cir);memset(on_circle, 0, sizeof on_circle);memset(cur_vis, 0, sizeof cur_vis);cir[1] = 1;has_circle = 0;for(int u = 2;u <= n; u++)if(del[u]) continue;else if(!cir[u]) dfs(u);return has_circle;
}
void update(){idx1 = 0;memset(h1, 0, sizeof h1);for(int u = 1;u <= n; u++){if(del[u]) continue;if(on_circle[u]){ans += w[id[u]];if(cir[u] != u) del[u] = 1;}for(int i = h[u];i;i = ne[i]){int j = e[i];if(cir[u] == cir[j]) continue;if(on_circle[u])add2(cir[u], cir[j], w[i] - w[id[u]]);else add2(u, cir[j], w[i]);}}memcpy(h, h1, sizeof h1);memcpy(e, e1, sizeof e1);memcpy(w, w1, sizeof w1);memcpy(ne, ne1, sizeof ne1);idx = idx1;
}
void solve(){ans = 0;memset(h, 0, sizeof h);memset(del, 0, sizeof del);idx = 0;for(int i = 1;i <= n; i++)scanf("%d%d", &p[i].a, &p[i].b);while(m--){int a, b;scanf("%d%d", &a, &b);add(b, a, dist(a, b));}bool flag = 0;while(true){if(!find_min()){flag = 1;break;}if(!find_circle()) {for(int i = 2;i <= n; i++) if(!del[i]) ans += w[id[i]];break;}update();}if(flag) puts("poor snoopy");else printf("%.2lf\n", ans);
}
int main(){while(~scanf("%d%d", &n, &m)) solve();return 0;
}