Aizu - 2224

题目链接：https://vjudge.net/problem/Aizu-2224

题目大意：

　　先给出 N 个点的坐标（x,y），这N个点之间有且只有M条边，接下来给出 M 条边的两端点，每条边对应的边权就是两端点的距离，断开一条边所需的花费就是这条边的边权。现在我们要断开一些边，使得剩余的边没有办法围成圈，但又要使得总花费最小。求所需的最小花费。

解题思路：

　　要是剩余的边没有办法围成圈，那么其实就是想要让剩余的边能够组成一棵树，所需的总花费其实就是除了这棵树以外的边的所有边权，所以我们让这颗树的权值最大，那么总花费（= 所有边的边权 - 树的总权值）就会最小。利用正难则反的思路，我们把这个问题转变成一道求最大生成树裸题。

　　Danger ! 记得考虑重边！

　　Danger！数组要开得足够大！

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 const int maxn=+;

 int fa[maxn];

 struct edge{

     int u,v;

     double cost;

 }es[maxn*maxn];

 struct node{

     int x,y;

 }cord[maxn];

 bool cmp(const edge &a,const edge &b){

     return a.cost>b.cost;

 }

 double cal(node a,node b){

     return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));

 }

 int finds(int rt){

     if(fa[rt]==rt)  return rt;

     return fa[rt]=finds(fa[rt]);

 }

 bool same(int a,int b){

     return finds(a)==finds(b);

 }

 int main(){

     int N,M;

     double tot=0.0;

     scanf("%d%d",&N,&M);

     for(int i=;i<=N;i++)    scanf("%d%d",&cord[i].x,&cord[i].y);

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

         scanf("%d%d",&es[i].u,&es[i].v);

         double c=cal(cord[es[i].u],cord[es[i].v]);

         es[i].cost+=c;

         tot+=c;

     }

     sort(es,es+M,cmp);

     for(int i=;i<=N;i++)    fa[i]=i;

     double res=0.0;

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

         edge e=es[i];

         if(!same(e.u,e.v)){

             int t1=finds(e.u),t2=finds(e.v);

             fa[t1]=t2;

             res+=e.cost;

         }

     }

     printf("%lf\n",tot-res);

     return ;

 }

巴特西

Aizu - 2224

最新文章

热门文章