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

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=755;
 7int n;
 8int m;
 9int om;
10pi ans[N*N];
11bool conc[N*N];
12int f[N];
13struct Edge
14{
15    int u,v;
16    double w;

1    bool operator < (Edge b)const
2    {
3	return w<b.w;
4    }
5}edge[N*N];

1struct point
2{
3    double  x,y;

1    void input()
2    {
3	scanf("%lf%lf",&x,&y);
4    }

1    double dis( point b)
2    {
3	double res ;
4	res = (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);
5	return sqrt(res);
6    }
7}p[N];

1void init()
2{
3    for ( int i = 1 ; i <= n ; i++) f[i] = i;
4}

1int root ( int x)
2{
3    if (x!=f[x] ) f[x] = root (f[x]);
4    return f[x];
5}

 1void merge( int x,int y)
 2{
 3    int rx = root (x);
 4    int ry = root (y);
 5    if (rx==ry) return ;
 6    f[rx] = ry;
 7}
 8int main()
 9{
10#ifndef  ONLINE_JUDGE 
11    freopen("code/in.txt","r",stdin);
12#endif

 1    cin>>n;
 2    init();
 3    for ( int i = 1 ; i <= n ; i++) p[i].input();
 4    cin>>m;
 5    om = m;
 6    int cnt = 0 ;
 7    for ( int i = 1 ; i <= m ; i++)
 8    {
 9	int u,v;
10	scanf("%d%d",&u,&v);
11	if (root(u)==root(v)) continue;
12	merge(u,v);
13	cnt++;
14    }

 1    m = 0 ;
 2    for ( int i = 1 ; i <= n ; i++)
 3	for ( int j = 1 ; j <= n ; j++)
 4	    if (i<j)
 5	    {
 6		m++;
 7		edge[m].u =i;
 8		edge[m].v = j ;
 9		edge[m].w = p[i].dis(p[j]);
10	    }

 1    sort(edge+1,edge+m+1);
 2    double mst = 0 ;
 3    int num = 0 ;
 4    for ( int i = 1; i <= m ; i++)
 5    {
 6	int u = edge[i].u;
 7	int v = edge[i].v;
 8	double w = edge[i].w;
 9	if (cnt>=n-1) break;
10	if (root(u)==root(v)) continue;
11	//	    cout<<"u:"<<u<<" v:"<<v<<" w:"<<w<<endl;
12	merge(u,v);
13	cnt++;
14	num++;
15	mst+=w;
16	ans[num]=make_pair(u,v);
17    }
18    //	cout<<"cnt:"<<cnt<<endl;
19    sort(ans+1,ans+num+1);

1#ifndef ONLINE_JUDGE  
2    fclose(stdin);
3#endif
4    return 0;
5}