题目描述：
有很多猫被困在一个图中，这些图由若干点组成，然后给了若干连线，把这个图分为了几个区域，请你求出把这个图消去若干条边，最后使这个图没有封闭区域，请问最小的花费是多少（花费等于边长总和）
思路：
一开始并没有头绪，后来发现把一个图变成一个没有封闭区域的图的最小花费=图的总权值-最大生成树的花费
然后就交了一发MST就过了
代码:
1 #include<cstdio> 2 #include<iostream> 3 #include <algorithm> 4 #include <cmath> 5 using namespace std; 6 const int maxn=1e4+5; 7 const int maxm=1e8+5; 8 int m,n,par[maxn],cnt; 9 struct edge 10 { 11 int fro,to; 12 double v; 13 }E[maxm]; 14 struct node 15 { 16 int x,y; 17 }poi[maxn]; 18 bool cmp(edge a,edge b) 19 { 20 return a.v>b.v; 21 } 22 double len(node a,node b) 23 { 24 int x=a.x-b.x,y=a.y-b.y; 25 return sqrt(x*x+y*y); 26 } 27 void add(int a,int b,double c) 28 { 29 E[cnt].fro=a; 30 E[cnt].to=b; 31 E[cnt++].v=c; 32 } 33 int find(int x) 34 { 35 int r=x; 36 while(r!=par[r]) r=par[r]; 37 int i=x,k; 38 while(i!=r) 39 { 40 k=par[i]; 41 par[i]=r; 42 i=k; 43 } 44 return r; 45 } 46 void unio(int x,int y) 47 { 48 x=find(x),y=find(y); 49 par[x]=y; 50 } 51 double Kruskal() 52 { 53 double ans=0; 54 for(int i=1;i<=maxn;i++) par[i]=i; 55 sort(E,E+cnt,cmp); 56 for(int i=0;i<cnt;i++) 57 { 58 edge e=E[i]; 59 if(find(e.fro)!=find(e.to)) 60 { 61 ans+=e.v; 62 unio(e.fro,e.to); 63 } 64 } 65 return ans; 66 } 67 int main() 68 { 69 double sum; 70 scanf("%d%d",&n,&m); 71 for(int i=1;i<=n;i++) 72 { 73 int x,y; 74 scanf("%d%d",&x,&y); 75 poi[i].x=x,poi[i].y=y; 76 } 77 for(int i=1;i<=m;i++) 78 { 79 int a,b; 80 scanf("%d%d",&a,&b); 81 double c=len(poi[a],poi[b]); 82 add(a,b,c); 83 sum+=c; 84 } 85 double ans=sum-Kruskal(); 86 printf("%.3lf ",ans ); 87 }