Description

Awson是某国际学校信竞组的一只菜鸡。他们班主任F老师喜欢带他们去爬爬唷喽山。登顶后,Awson有了个奇怪的发现。

山腰上有N(1<=N<=100)个村庄,这些村庄可以用平面坐标(X,Y)刻画。假设要给这N个村庄供水。已知1号村庄内有一个处理水厂, 从此处可以输水给其他各个村庄。现在给出M(1<=M<=10000)种修水渠的方案,每种方案的水渠连接两个村庄U,V。由于地势等其他原 因,水的运输是单向的,即只能从U运输到V。水渠是笔直的,即水渠的长度就是U,V两村庄的欧式距离。因为Awson是一个善于发现问题、提出问题,但不 喜欢解决问题的人。所以他找到了你,烦请你设计出能够将水输送到所有村庄的方案,并且使水渠总长度最小。

Input

第1行:两个整数,N,M。

接下来N行,每行两个整数,第i行Xi,Yi,表示村庄的坐标。

再接下来M行,每行两个整数,第i行Ui,Vi,表示Ui,Vi两村庄间有一条从Ui到Vi的修水渠方案。

Output

共1行,1个整数,表示使所有机房连上网的费用最小值。

Sample Input1

4 60 64 60 07 201 21 32 33 43 13 2

Sample Output1

31.19

Sample Input2

4 3
0 0
1 0
0 1
1 2
1 3
4 1
2 3

Sample Output2

poor Awson

Hint

样例解释:

对于样例1:选择第1、2、4方案,长度最小,其为31.19;

对于样例2:没有方案使其连通。

数据规模:

40%的数据:1<=N<=50,1<=M<=2500;

100%的数据:1<=N<=100,1<=M<=10000,1<=X,Y<=10000,数据不保证无自环,不保证无重边、回边。

题解

朱刘算法裸题,当模板存着。

 #include<map>
 #include<queue>
 #include<stack>
 #include<vector>
 #include<ctime>
 #include<cmath>
 #include<cstdio>
 #include<string>
 #include<cstdlib>
 #include<cstring>
 #include<iostream>
 #include<algorithm>
  using namespace std;
 ;

 struct node
 {
     int x,y;
 }pos[N+];
 struct tt
 {
     int u,v;
     double c;
 }edge[N*N+];
 int n,m,u,v;
 inline double Dist(int u,int v);

 ];
 ];
 ];
 ],cnt;
 double ZLEdmons();

 int main()
 {
     scanf("%d%d",&n,&m);
     ;i<=n;i++) scanf("%d%d",&pos[i].x,&pos[i].y);
     ]={};
     ;i<=m;i++)
     {
         scanf("%d%d",&u,&v);
         edge[i].v=v;
         edge[i].u=u;
         edge[i].c=Dist(u,v);
         ;
     }
     ;i<=n;i++) if (!in[i])
     {
         printf("poor Awson\n");
         ;
     }
     printf("%.2lf\n",ZLEdmons());
     ;
 }

 inline double Dist(int u,int v){return sqrt((pos[u].x-pos[v].x)*(pos[u].x-pos[v].x)+(pos[u].y-pos[v].y)*(pos[u].y-pos[v].y));}
 double ZLEdmons()
 {
     ;
     ;
     while (true)
     {
         memset(,sizeof(in));
         ;i<=m;i++)
         {
             if (edge[i].c<in[edge[i].v]&&edge[i].u!=edge[i].v)
             {
                 in[edge[i].v]=edge[i].c;
                 pre[edge[i].v]=edge[i].u;
             }
         }
         ;
         ;
         memset(id,-,sizeof(id));
         memset(vis,-,sizeof(vis));
         ;i<=n;i++)
         {
             ans+=in[i];
             v=i;
             )
             {
                 vis[v]=i;
                 v=pre[v];
             }
             )
             {
                 id[v]=++cnt;
                 for (int u=pre[v];u!=v;u=pre[u]) id[u]=cnt;
             }
         }
         ) break;
         ;i<=n;i++) ) id[i]=++cnt;
         ;i<=m;i++)
         {
             v=edge[i].v;
             edge[i].u=id[edge[i].u];
             edge[i].v=id[edge[i].v];
             if (edge[i].u!=edge[i].v) edge[i].c-=in[v];
         }
         n=cnt;
         root=id[root];
     }
     return ans;
 }
05-11 14:42