uva 10147 Highways

解題：Partial 'Minimum' Spanning Tree
將固定邊連接，再做Kruskal
Code：

  1  #include<stdio.h>

  2  #include<stdlib.h>

  3  #include<iostream>

  4  #include<algorithm>

  5  #include<vector>

  6  #include<queue>

  7  #include<math.h>

  8  #include<utility>

  9  #include<string.h>

 10  #define MAXN 800

 11  using namespace std;

 12  typedef pair<double,double> ii;

 13  int g[MAXN]={0};

 14  vector<ii> ans;

 15  int initial()

 16  {

 17      for(int i=0; i<MAXN; i++) g[i]=i;

 18  }

 19  int Find(int a)

 20  {

 21      if(g[a]!=a)

 22      {

 23          g[a]=Find(g[a]);

 24      }

 25      return g[a];

 26  }

 27  void Union(int a,int b)

 28  {

 29      if(Find(a)!=Find(b))

 30      {

 31          g[g[a]]=g[b];

 32      }

 33  }

 34  void kruskal(priority_queue<pair<double,ii> > &pq)

 35  {

 36      while(!pq.empty())

 37      {

 38          pair<double,ii> top=pq.top();

 39          pq.pop();

 40          int x=top.second.first,y=top.second.second;

 41          if(Find(x)!=Find(y))

 42          {

 43              Union(x,y);

 44              ans.push_back(ii(x,y));

 45          }

 46      }

 47  }

 48  double dist(double x1,double x2,double y1,double y2)

 49  {

 50      return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

 51  }

 52  int main()

 53  {

 54      int cas;

 55      while(cin>>cas)

 56      {

 57          for(int c=0; c<cas; c++)

 58          {

 59              if(c) cout<<endl;

 60              memset(g,0,sizeof(g));

 61              ii pos[MAXN];

 62              ans.clear();

 63              priority_queue<pair<double,ii> > pq;

 64              int n;

 65              cin>>n;

 66              for(int i=1; i<=n; i++)

 67              {

 68                  cin>>pos[i].first>>pos[i].second;

 69              }

 70              for(int i=1; i<=n-1; i++)

 71              {

 72                  for(int j=i+1; j<=n; j++)

 73                  {

 74                      double len=dist(pos[i].first,pos[j].first,pos[i].second,pos[j].second);

 75                      pq.push(make_pair(0.0-len,ii(i,j)));

 76                  }

 77              }

 78              int m;

 79              cin>>m;

 80              initial();

 81              for(int i=0; i<m; i++)

 82              {

 83                  int a,b;

 84                  cin>>a>>b;

 85                  Union(a,b);

 86              }

 87              kruskal(pq);

 88              if(ans.empty()) printf("No new highways need\n");

 89              else

 90              {

 91                  for(int i=0; i<ans.size(); i++)

 92                  {

 93                      cout<<ans[i].first<<' '<<ans[i].second<<endl;

 94                  }

 95              }

 96          }

 97      }

 98      return 0;

 99  }