裸最小生成树。用kauskal做方便一些。
不得不说这么大数据用cin cout 真是作死。。活该T那么多次。。。
/*************************************************
Problem: 1751User: G_lory
Memory: 4640KTime: 594MS
Language: C++Result: Accepted
*************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>using namespace std;const int MAXN = 755;
const int MAXM = MAXN * MAXN;int par[MAXN];
int rk[MAXN];struct Edge
{
int u, v;
double w;
bool operator<(const Edge a) const
{
return w < a.w;
}
} edge[MAXM];int tol;void addedge(int u, int v, double w)
{
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}void init(int n)
{
for (int i = 0; i <= n; ++i)
{
rk[i] = 0;
par[i] = i;
}
}int find(int x)
{
if (par[x] == x) return x;
return par[x] = find(par[x]);
}void unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) return ;
if (rk[x] < rk[y]) par[x] = y;
else par[y] = x;
if (rk[x] == rk[y]) rk[x]++;
}void Kruskal(int n, int m)
{
sort(edge, edge + tol);
int cnt = 0;
for (int i = 0; i < tol; i++)
{
int t1 = find(edge[i].u);
int t2 = find(edge[i].v);
if (t1 != t2)
{
cout << edge[i].u << " " << edge[i].v << endl;
unite(t1, t2);
cnt++;
}
if (cnt == n - 1 - m) break;
}
}struct Point {
double x, y;
double dis(Point a)
{
return sqrt( (x - a.x) * (x - a.x) + (y - a.y) * (y - a.y) );
}
} p[MAXN];int main()
{
int n, m;
scanf("%d", &n);
tol = 0;
for (int i = 1; i <= n; ++i)
scanf("%lf%lf", &p[i].x, &p[i].y);
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
addedge(i, j, p[i].dis(p[j]));
init(n);
scanf("%d", &m);
int a, b;
int p = 0;
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &a, &b);
if (find(a) != find(b))
{
unite(a, b);
++p;
}
}
Kruskal(n, p);
return 0;
}