UESTC_秋实大哥与连锁快餐店 2015 UESTC Training for Graph Theory<Problem A>

A - 秋实大哥与连锁快餐店

Time Limit: 9000/3000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

成大事者，不惟有超世之才，亦有坚忍不拔之志。

秋实大哥开了一家快餐店之后，由于人赢光环的影响，很快就赚得了大量的资金。为了继续实现心中的远大的理想，他打算在全国各地开设分店赚大钱。假设现在有n家快餐店（其中有至少有一家是旗舰店）分布在二维平面上，第i家快餐店的坐标为（xi, yi）。为了方便交通，他打算在一些快餐店之间修建道路使得任意一家快餐店都能够通过道路到达某一家旗舰店。

但是秋实大哥忙于赚钱和过节，没有时间来设计道路，你能帮助秋实大哥算出最少一共需要修建多长的道路吗？

Input

第一行一个整数n，表示快餐店的个数。(n≤6666) 接下来n行，每行两个整数xi,yi,zi(−1000000≤xi,yi≤1000000)。表示第i家快餐店的位置(xi,yi)，如果zi=0表示该店是普通的分店，如果 zi=1表示该店是旗舰店。

保证至少有一家旗舰店

Output

输出最少一共需要修建的道路长度，保留小数点后两位。

Sample input and output

Sample Input	Sample Output
3 1 -1 0 1 1 0 0 0 1	2.83

解题思路：

 我们注意到每个普通店都需要连接至少一个旗舰店，但是旗舰店之间并没有要求，那么我们可以认为所有旗舰店都已被连接，不过它们连接的代价是 0 罢了，这样，我们就成功的把这道题转换成了一道最小生成树题目.

 最小生成树拥有Prim 和 Krusal 算法，但是本题显然是稠密图，因此我们采用Prim算法跑一遍即可.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 6666 + 50;
/*
 Prim Algorithm
 0 -> 普通店
 1 -> 旗舰店 
*/

typedef struct Point
{
  double x,y;    
  char type;
};


Point p[maxn];
double lowcost[maxn];
int n;
double ans = 0.;

inline double distant(int u,int v)
{
   return sqrt( (p[u].x - p[v].x)*(p[u].x - p[v].x) + (p[u].y - p[v].y)*(p[u].y - p[v].y) );
}

void prim()
{
   for(int i = 0 ; i < n ; ++ i)
    if (p[i].type) //旗舰店 
     {
         lowcost[i] = -1.;
         for(int j = 0 ; j < n ; ++ j)
          {
             double dis = distant(i,j);
             lowcost[j] = min(lowcost[j] , dis);
         }
     }
   for(int i = 0 ; i < n ; ++ i)
    {
        double minval = 1e233;
        int choosepoint = -1;
        for(int j = 0 ; j < n ; ++ j)
         {
             if (lowcost[j] != -1 && lowcost[j] < minval)
              {
                 minval = lowcost[j];
                choosepoint = j;    
             }
         }
        if (choosepoint == -1)
         return;
        ans += lowcost[choosepoint];
        lowcost[choosepoint] = -1;
        for(int j = 0 ; j < n ; ++ j)
         {
             double dis = distant(choosepoint,j);
             lowcost[j] = min(lowcost[j],dis);
         }
    }
}


int main(int argc,char *argv[])
{
  scanf("%d",&n);
  for(int i = 0 ; i < n ; ++ i) lowcost[i] = 1e233;
  for(int i = 0 ; i < n ; ++ i)
   scanf("%lf%lf%d",&p[i].x,&p[i].y,&p[i].type);
  prim();
  printf("%.2lf
",ans);
  return 0;
}