Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：一开始有一些边，然后添加一些边，使得代价之和最小。
思路：先把给定的边merge掉。。然后计算其余可以添加的边。。。接下来就是最小生成树。。。
然而因为多开了一个750*750的数组空间被卡了常。。。毫无人性。。。。
代码实现
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}