avatar
fireworks99
keep hungry keep foolish

POJ 3164 Command Network(Minimum tree-shape graph)

Description

N个点M条有向边,求以1位根节点最小树形图(有向最小生成树)

朱刘算法

①选出入边集:找到除root点之外,每一个点的所有入边中权值最小的,用数组in[]记录下这个最小权值,用pre[]记录到达该点的前驱。判断是否存在无入边的点(除了root),若有,则无法成树。

②找有向环:倘若无环,则该入边集就是最小树形图,算法结束。

若有环,说明未成树,做缩点前期工作:记下环上每个点所属环的标号。

③缩点中期工作:将不属于环上的点“缩点”

④缩点后期工作:更新缩点后的图中的边的权值。因为我们在过程中“误+”了环中某一边,此时要减掉。重复以上过程。

Code

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 105; const int INF = 0x3f3f3f3f; int n, m, id[N], pre[N], vis[N]; double x[N], y[N], in[N]; struct edge { int u, v; double w; }e[4 * N * N]; double getDis(double x, double y, double xx, double yy) { return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy)); } double zhuliu(int root) { int u, v; double res = 0; while(true) { ///①.Set of in for(int i = 1; i <= n; ++i) in[i] = -1.0; for(int i = 1; i <= m; ++i) if(e[i].u != e[i].v && (e[i].w < in[ e[i].v ] || in[ e[i].v ] < 0)) in[ e[i].v ] = e[i].w, pre[ e[i].v ] = e[i].u; for(int i = 1; i <= n; ++i) if(i != root && in[i] < 0) return -1.0; ///②.Directed circle int cnt = 1; memset(id, -1, sizeof(id)); memset(vis,-1, sizeof(vis)); in[root] = 0; for(int i = 1; i <= n; ++i) { res += in[i]; v = i; while(id[v] == -1 && v != root && vis[v] != i) vis[v] = i, v = pre[v]; if(id[v] == -1 && v != root)/// vis[v] == i { for(u = pre[v]; u != v; u = pre[u]) id[u] = cnt; id[v] = cnt++; } } ///③.No circle -> Over if(cnt == 1) break; ///④.Process other nodes ,and then "shrink". for(int i = 1; i <= n; ++i) if(id[i] == -1) id[i] = cnt++; for(int i = 1; i <= m; ++i) { v = e[i].v; e[i].u = id[ e[i].u ]; e[i].v = id[ e[i].v ]; if(e[i].u != e[i].v) e[i].w -= in[v];///This v is the original v! } n = cnt - 1; root = id[root]; } return res; } int main() { while(~scanf("%d %d", &n, &m)) { for(int i = 1; i <= n; ++i) scanf("%lf %lf", &x[i], &y[i]); int u, v; for(int i = 1; i <= m; ++i) { scanf("%d %d", &u, &v); e[i].u = u, e[i].v = v; e[i].w = getDis(x[u], y[u], x[v], y[v]); } double ans = zhuliu(1); if(ans < 0) cout << "poor snoopy" << '\n'; else printf("%.2f\n", ans); } }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy