poj 1751 Highways (最小生成树，空间卡常数有毒啊)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年07月13日 星期三 19时53分29秒
  4File Name :code/poj/1751.cpp
  5 ************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=755;
 34int n;
 35int m;
 36int om;
 37pi ans[N*N];
 38bool conc[N*N];
 39int f[N];
 40struct Edge
 41{
 42    int u,v;
 43    double w;
 44
 45    bool operator < (Edge b)const
 46    {
 47	return w<b.w;
 48    }
 49}edge[N*N];
 50
 51
 52
 53struct point
 54{
 55    double  x,y;
 56
 57    void input()
 58    {
 59	scanf("%lf%lf",&x,&y);
 60    }
 61
 62    double dis( point b)
 63    {
 64	double res ;
 65	res = (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);
 66	return sqrt(res);
 67    }
 68}p[N];
 69
 70void init()
 71{
 72    for ( int i = 1 ; i <= n ; i++) f[i] = i;
 73}
 74
 75int root ( int x)
 76{
 77    if (x!=f[x] ) f[x] = root (f[x]);
 78    return f[x];
 79}
 80
 81void merge( int x,int y)
 82{
 83    int rx = root (x);
 84    int ry = root (y);
 85    if (rx==ry) return ;
 86    f[rx] = ry;
 87}
 88int main()
 89{
 90#ifndef  ONLINE_JUDGE 
 91    freopen("code/in.txt","r",stdin);
 92#endif
 93
 94    cin>>n;
 95    init();
 96    for ( int i = 1 ; i <= n ; i++) p[i].input();
 97    cin>>m;
 98    om = m;
 99    int cnt = 0 ;
100    for ( int i = 1 ; i <= m ; i++)
101    {
102	int u,v;
103	scanf("%d%d",&u,&v);
104	if (root(u)==root(v)) continue;
105	merge(u,v);
106	cnt++;
107    }
108
109    m = 0 ;
110    for ( int i = 1 ; i <= n ; i++)
111	for ( int j = 1 ; j <= n ; j++)
112	    if (i<j)
113	    {
114		m++;
115		edge[m].u =i;
116		edge[m].v = j ;
117		edge[m].w = p[i].dis(p[j]);
118	    }
119
120    sort(edge+1,edge+m+1);
121    double mst = 0 ;
122    int num = 0 ;
123    for ( int i = 1; i <= m ; i++)
124    {
125	int u = edge[i].u;
126	int v = edge[i].v;
127	double w = edge[i].w;
128	if (cnt>=n-1) break;
129	if (root(u)==root(v)) continue;
130	//	    cout<<"u:"<<u<<" v:"<<v<<" w:"<<w<<endl;
131	merge(u,v);
132	cnt++;
133	num++;
134	mst+=w;
135	ans[num]=make_pair(u,v);
136    }
137    //	cout<<"cnt:"<<cnt<<endl;
138    sort(ans+1,ans+num+1);
139
140    for ( int i = 1 ;i <= num ; i++)
141	cout<<ans[i].fst<<" "<<ans[i].sec<<endl;
142
143
144
145#ifndef ONLINE_JUDGE  
146    fclose(stdin);
147#endif
148    return 0;
149}