[Awson原创]修水渠(canal)

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

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;
 }

秒客网