Aizu2224 Save your cats（最大生成树）

场景嵌入得很好，如果不是再最小生成树专题里，我可能就想不到解法了。

对所有的边（栅栏）求最大生成树，剩下来的长度即解（也就是需要破环的最小边和）。

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<stack>

 #define lson l, m, rt<<1

 #define rson m+1, r, rt<<1|1

 #define IO ios::sync_with_stdio(false);cin.tie(0);

 #define INF 0x3f3f3f3f

 typedef unsigned long long ll;

 using namespace std;

 int pre[];

 typedef struct{

     int x, y;

     double w;

 }Node;

 Node node[];

 double length(int a, int b)

 {

     return sqrt(a*a+b*b);

 }

 bool cmp(const Node a, const Node b)

 {

     return a.w>b.w;

 }

 int find(int x)

 {

     while(x != pre[x])

         x = pre[x];

     return x;

 }

 int main()

 {

     int n, m, a[], b[], s, t;

     while(cin >> n >> m){

         for(int i = ; i <= n; i++){

             pre[i] = i;

         }

         double ans = , sum=;

         for(int i = ; i <= n; i++){

             cin >> a[i] >> b[i];

         }

         for(int i = ; i < m; i++){

             cin >> s >> t;

             double tmp = length(a[s]-a[t], b[s]-b[t]);

             node[i].x = s; node[i].y = t;

             node[i].w = tmp;

             sum+=tmp;

         }

         sort(node, node+m, cmp);

         for(int i = ; i < m; i++){

             int tx = find(node[i].x);

             int ty = find(node[i].y);

             if(tx != ty){

                 pre[tx] = ty;

                 ans += node[i].w;

             }

         }

         printf("%.3lf\n", sum-ans);

     }

     return ;

 }