（最小树形图）POJ 3164

题意：

给定一个有向图，求以某个给定顶点为根的有向生成树（也就是说沿着这N-1条有向边可以从根走到任一点），使权和最小。

分析：

这题直接朱刘算法，虽然看起来很偏门，但是还是要学一下。算法过程很多博客都有了，这里就不赘述了。

不过貌似CSU1828是朱刘算法+AC自动机，可以刷一刷。

代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <vector>
  6 #include <cmath>
  7 
  8 using namespace std;
  9 
 10 const int inf = 0x3f3f3f3f;
 11 const int maxn = 110;
 12 
 13 
 14 int n, m;
 15 double x[maxn], y[maxn];
 16 
 17 double dis(double x1, double y1, double x2, double y2) {
 18     return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
 19 }
 20 
 21 struct Edge {
 22     int u, v;
 23     double c;
 24 };
 25 
 26 Edge edge[10010];
 27 
 28 double in[maxn];
 29 int pre[maxn];
 30 int id[maxn];
 31 int vis[maxn];
 32 
 33 double MTV(int root) {
 34     double ans = 0;
 35     while(1) {
 36         for(int i = 0; i < n; i++) in[i] = inf;
 37         for(int i = 0; i < m; i++) {
 38             int u = edge[i].u;
 39             int v = edge[i].v;
 40             if(edge[i].c < in[v] && u != v) {
 41                 in[v] = edge[i].c;
 42                 pre[v] = u;
 43             }
 44         }
 45 
 46         for(int i = 0; i < n; i++) {
 47             if(i == root) continue;
 48             if(in[i] == inf) return -1;
 49         }
 50 
 51         int cnt = 0;
 52         memset(id, -1, sizeof(id));
 53         memset(vis, -1, sizeof(vis));
 54         in[root] = 0;
 55         for(int i = 0; i < n; i++) {
 56             ans += in[i];
 57             int v = i;
 58             while(vis[v] != i && id[v] == -1 && v != root) {
 59                 vis[v] = i;
 60                 v = pre[v];
 61             }
 62             if(v != root && id[v] == -1) {
 63                 for(int u = pre[v]; u != v; u = pre[u]) {
 64                     id[u] = cnt;
 65                 }
 66                 id[v] = cnt++;
 67             }
 68         }
 69         if(cnt == 0) break;
 70 
 71         for(int i = 0; i < n; i++) {
 72             if(id[i] == -1) id[i] = cnt++;
 73         }
 74 
 75         for(int i = 0; i < m; i++) {
 76             int v = edge[i].v;
 77             edge[i].v = id[edge[i].v];
 78             edge[i].u = id[edge[i].u];
 79             if(edge[i].u != edge[i].v) {
 80                 edge[i].c -= in[v];
 81             }
 82         }
 83         n = cnt;
 84         root = id[root];
 85     }
 86     return ans;
 87 }
 88 
 89 
 90 
 91 int main() {
 92     while(~scanf("%d%d", &n, &m)) {
 93         for(int i = 0; i < n; i++) {
 94             scanf("%lf%lf", &x[i], &y[i]);
 95         }
 96         for(int i = 0; i < m; i++) {
 97             int u, v;
 98             scanf("%d%d", &u, &v);
 99             u--, v--;
100             if(u == v)edge[i] = Edge{u, v, inf};
101             else edge[i] = Edge{u, v, dis(x[u], y[u], x[v], y[v])};
102         }
103         double ans = MTV(0);
104         if(ans < 0)puts("poor snoopy");
105         else printf("%.2f
", ans);
106     }
107 
108     return 0;
109 
110 }

（最小树形图）POJ 3164

相关推荐