撰写Flatopian towns are numbered from 1 to N and town i has a position given by the Cartesian coordinates (xi, yi). Each highway connects exaclty two towns. All highways (both the original ones and the ones that are to be built) follow straight lines, and thus their length is equal to Cartesian distance between towns. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.
The Flatopian government wants to minimize the cost of building new highways. However, they want to guarantee that every town is highway-reachable from every other town. Since Flatopia is so flat, the cost of a highway is always proportional to its length. Thus, the least expensive highway system will be the one that minimizes the total highways length.
Input
The first line of the input file contains a single integer N (1 <= N <= 750), representing the number of towns. The next N lines each contain two integers, xi and yi separated by a space. These values give the coordinates of i th town (for i from 1 to N). Coordinates will have an absolute value no greater than 10000. Every town has a unique location.
The next line contains a single integer M (0 <= M <= 1000), representing the number of existing highways. The next M lines each contain a pair of integers separated by a space. These two integers give a pair of town numbers which are already connected by a highway. Each pair of towns is connected by at most one highway.
Output
If no new highways need to be built (all towns are already connected), then the output file should be created but it should be empty.
Sample Input
9 1 5 0 0 3 2 4 5 5 1 0 4 5 2 1 2 5 3 3 1 3 9 7 1 2
题意：给你一些连接好的边权为0的边和一些坐标，输出最小树的其他边
题解：标记一下，用prim会好些，但是我懒
代码：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn=1e4+5;
const int maxm=1e6+5;
int F[maxn];
int tol;
int find(int x){
return F[x]==-1?x:F[x]=find(F[x]);
}
struct Edge{
int u;
int v;
int w;
}edge[maxm];
void addedge(int u,int v,int w){
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
bool cmp(Edge &a, Edge &b){
return a.w<b.w;
}
void Kruskal(int n)//传入点数，返回最小生成树的权值，如果不连通返回-1
{
memset(F,-1,sizeof(F));
sort(edge,edge+tol,cmp);
int cnt=0;//计算加入的边数
for(int i=0;i<tol;i++) {
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int t1=find(u);
int t2=find(v);
if(t1!=t2) {
F[t1]=t2;
cnt++;
if(w!=-1)printf("%d %d\n",u,v);
}
if(cnt==n-1)break;
}
}
pair<int,int>p[1014];
int dist(int i,int j){
return (p[i].first-p[j].first)*(p[i].first-p[j].first)+(p[i].second-p[j].second)*(p[i].second-p[j].second);
}
int vis[maxm];
int main(){
tol=0;
int n,m;
CLR(vis);
scanf("%d",&n);
rep(i,1,n)scanf("%d%d",&p[i].first,&p[i].second);
scanf("%d",&m);
int x,y;
rep(i,1,m){
scanf("%d%d",&x,&y);
if(x>y)swap(x,y);
vis[x*1000+y]=1;
}
rep(i,1,n)
rep(j,1,n){
if(j>i&&!vis[i*1000+j])addedge(i,j,dist(i,j));
else if(j>i&&vis[i*1000+j])addedge(i,j,-1);
}
Kruskal(n);
return 0;
}