[Aizu2224] Save your cats

题意：女（gua）巫（fu）建立了N个魔法桩，魔法桩之间连了M条魔法栅栏，形成了一个个封闭图形，困住了小（na）猫（er）们，你要砍掉一些魔法栅栏，使得小猫们能顺利逃脱

题解：

最大生成树

当图形形成一棵树时，才恰好不是封闭图形

构出最大生成树，未加入树的边的和即为答案

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #define ll long long
 8 using namespace std;
 9 
10 const int N = 10010;
11 
12 int n,m,k,fa[N];
13 bool vis[N*100];
14 double ans;
15 
16 int find(int x) {
17   return x==fa[x]?x:fa[x]=find(fa[x]);
18 }
19 
20 struct Node {double x,y;}p[N];
21 struct Edge {
22   int x,y; double z;
23   bool operator < (const Edge &a) const {
24     return z>a.z;
25   }
26 }e[N*100];
27 
28 int gi() {
29   int x=0,o=1; char ch=getchar();
30   while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
31   if(ch=='-') o=-1,ch=getchar();
32   while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
33   return o*x;
34 }
35 
36 double cal(int i, int j) {
37   return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
38 }
39 
40 int main() {
41   n=gi(),m=gi();
42   for(int i=1; i<=n; i++) {
43     scanf("%lf%lf", &p[i].x, &p[i].y);    
44   } 
45   for(int i=1; i<=m; i++) {
46     int x=gi(),y=gi();
47     double dis=cal(x,y);
48     e[i]=(Edge){x,y,dis};
49   }
50   sort(e+1,e+m+1);
51   for(int i=1; i<=n; i++) fa[i]=i;
52   for(int i=1; i<=m; i++) {
53     int x=e[i].x,y=e[i].y,xx,yy;
54     xx=find(x),yy=find(y);
55     if(xx==yy) continue; 
56     fa[yy]=xx;
57     vis[i]=1,k++;
58     if(k==n-1) break;
59   }
60   for(int i=1; i<=m; i++) {
61     if(!vis[i]) ans+=e[i].z;
62   } 
63   printf("%.3f", ans);
64   return 0;
65 }