poj 3164 Command Network

本文从WordPress迁移而来, 查看全部WordPress迁移文章

最小树形图

题意:给出每个点的坐标,给出有向边,判断是否存在最小树形图,存在的话输出最小权和,模板题

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 110
#define M 10010
#define INF 10000000000.0
#define cl memset

double x[N],y[N];
int n,tot;
struct edge{
int u,v,next;
double w;
}e[M];
int pre[N],id[N],vis[N];
double in[N];

inline double dis(int i,int j){
return sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
}
inline void add(int u,int v){
e[tot].u = u; e[tot].v = v; e[tot++].w = dis(u,v);
}

double Directed_MST(int root,int nv,int ne){
double res = 0;
while(true){
//1.最小入边
for(int i = 0; i < nv; i++) in[i] = INF;
for(int i = 0; i < ne; i++){
int u = e[i].u , v = e[i].v;
double w = e[i].w;
if(u != v && w < in[v]){
in[v] = w; pre[v] = u;
}
}
for(int i = 0; i < nv; i++){
if(i == root) continue;
if(in[i] == INF) return -1;
}

//2.找环
int cntnode = 0;
for(int i = 0; i < nv; i++){
id[i] = vis[i] = -1;
}
in[root] = 0;
for(int i = 0; i < nv; i++){
res += in[i];
int v = i;
while(vis[v] != i && id[v] == -1 && v != root){
vis[v] = i; v = pre[v];
}
if(v != root && id[v] == -1){
for(int u = pre[v]; u != v; u = pre[u])
id[u] = cntnode;
id[v] = cntnode++;
}
}
if(cntnode == 0) break;
for(int i = 0; i < nv; i++)
if(id[i] == -1)
id[i] = cntnode++;
//3.重新建图
for(int i = 0; i < ne; i++){
int temp = 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[temp];
}
nv = cntnode;
root = id[root];
}
return res;
}

int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
tot = 0;
for(int i = 0 ; i < n; i++)
scanf("%lf%lf",&x[i],&y[i]);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
if(u == v) continue;
add(--u,--v);
}
double ans;
if( (ans = Directed_MST(0,n,tot)) == -1)
printf("poor snoopy\n");
else
printf("%.2f\n",ans);
}
return 0;
}