POJ 3164 Command Network 最小树形图-朱刘算法裸题

本文主要是介绍POJ 3164 Command Network 最小树形图-朱刘算法裸题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：POJ 3164 Command Network

题意：求以1为根的最小树形图 没有输出字符串

思路：直接高朱刘算法 不懂的可以百度 学会了就是直接套模板的事情 其实就是不断消圈而已 不构成圈就有解 无法从根到达其他点就无解

 

#include <cstdio>
#include <cstring>
#include <cmath>
const int maxn = 110;
const int maxm = 50010;
const double INF = 999999999;
struct edge
{int u, v;double w;edge(){}edge(int u, int v, double w) : u(u), v(v), w(w){}
}e[maxm];struct Point
{double x, y;
}p[maxn];int pre[maxn], vis[maxn], no[maxn];
double in[maxn];
double dis(Point a, Point b)  
{  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));  
}  
double MST(int n, int m, int rt)
{double ans = 0;while(1){for(int i = 1; i <= n; i++)in[i] = INF;for(int i = 1; i <= m; i++){int u = e[i].u;int v = e[i].v;if(u != v && in[v] > e[i].w){pre[v] = u;in[v] = e[i].w;}}for(int i = 1; i <= n; i++){if(i == rt)continue;if(in[i] == INF)return -1;}memset(no, -1, sizeof(no));memset(vis, -1, sizeof(vis));in[rt] = 0;int cnt = 0;for(int i = 1; i <= n; i++){ans += in[i];int v = i;while(v != rt && vis[v] != i && no[v] == -1){vis[v] = i;v = pre[v];}if(v != rt && no[v] == -1){for(int u = pre[v]; u != v; u = pre[u])no[u] = cnt+1;no[v] = cnt+1;cnt++;}}if(!cnt)return ans;for(int i = 1; i <= n; i++)if(no[i] == -1)no[i] = ++cnt;for(int i = 1; i <= m; i++){int u = e[i].u;int v = e[i].v;e[i].u = no[u];e[i].v = no[v];if(no[u] != no[v]){e[i].w -= in[v];}}n = cnt;rt = no[rt];}return ans;
}
int main()
{int n, m;while(scanf("%d %d", &n, &m) != EOF){for(int i = 1 ; i <= n; i++)scanf("%lf %lf", &p[i].x, &p[i].y);int add = 1;for(int i = 1; i <= m; i++){scanf("%d %d", &e[add].u, &e[add].v);if(e[add].u == e[add].v)continue;e[add].w = dis(p[e[add].u], p[e[add].v]);add++;}double ans = MST(n, add-1, 1);if(ans < 0)puts("poor snoopy");elseprintf("%.2f\n", ans);}return 0;
}

 

 

这篇关于POJ 3164 Command Network 最小树形图-朱刘算法裸题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---