Difference between
modified post 30bde by Anonymous on Sun 4th Dec 2011 03:23
original post 9dee88bce by Anonymous on Sun 4th Dec 2011 03:18
Download diff
Show old version | new version | both versions

#include <math.h>

1	1		#include <math.h>
2	2		#include <stdio.h>
3	3		#include <stdlib.h>
4	4
5	5		#define TRUE 1
6	6		#define FALSE 0
7	7		#define DEBUG 0
8	8
9	9		#define MAX_TOWNS 752
10	10
11	11		typedef struct Highway Highway;
12	12		struct Highway {
13	13		int from, to, done, old;
14	14		double distance;
15	15		};
16	16
17	17		typedef struct City City;
18	18		struct City {
19	19		int x, y, connected;
20	20		};
21	21
22	22		int highways_done;
23	23		int highways_count;
24	24		Highway highways[(MAX_TOWNS*MAX_TOWNS)/2];
25	25
26	26		int sets_count;
	27	+	int sets_luid;
27	28		int sets[MAX_TOWNS];
28	29
29	30		int cities_count;
30	31		int cities_connected;
31	32		City cities[MAX_TOWNS];
32	33
33	34		double distance(int from, int to){
34	35		return sqrt((cities[from].x-cities[to].x)((cities[from].x-cities[to].x))+(cities[from].y-cities[to].y)(cities[from].y-cities[to].y));
35	36		}
36	37
37	38		Highway *highway(int from, int to){
38	39		if(from == to) return NULL;
39	40
40	41		if(from < to){
41	42		return &highways[from+(to-1)*to/2];
42	43		}else{
43	44		return highway(to, from);
44	45		}
45	46		}
46	47
47	48		int create_cicles(Highway *hw){
48	49		if(sets[hw->from] == -1) return FALSE;
49	50		if(sets[hw->to] == -1) return FALSE;
50	51		if(sets[hw->from] == sets[hw->to]) return TRUE;
51	52		return FALSE;
52	53		}
53	54
54	55		void merge_sets(int from, int to){
55	56		int i, set_id;
56	57
57	58		if(sets[from] == -1 && sets[from] == sets[to]){
58		-	sets[to] = sets_count;
	59	+	sets[to] = sets_luid;
59		-	sets[from] = sets_count;
	60	+	sets[from] = sets_luid;
	61	+	sets_luid++;
60	62		sets_count++;
61	63		return;
62	64		}
63	65
64	66		if(sets[from] == -1){
65	67		sets[from] = sets[to];
66	68		return;
67	69		}
68	70
69	71		if(sets[to] == -1){
70	72		sets[to] = sets[from];
71	73		return;
72	74		}
73	75
74	76		if(sets[from] == sets[to]) return;
75	77
76		-	for(i = 0; i < cities_count; i++){
77	78		set_id = sets[to];
	79	+	for(i = 0; i < cities_count; i++){
78	80		if(set_id == sets[i]){
79	81		sets[i] = sets[from];
80	82		}
81	83		}
82	84		if(sets_count > 1) sets_count--;
83	85		}
84	86
85	87		int ended(){
86	88		if(cities_connected == cities_count && sets_count == 1) return TRUE;
87	89		return FALSE;
88	90		}
89	91
90	92		void build_highway(Highway *hw){
91	93		if(!cities[hw->to].connected){
92	94		cities[hw->to].connected = TRUE;
93	95		cities_connected++;
94	96		}
95	97
96	98		if(!cities[hw->from].connected){
97	99		cities[hw->from].connected = TRUE;
98	100		cities_connected++;
99	101		}
100	102
101	103		merge_sets(hw->from, hw->to);
102	104		hw->done = TRUE;
103	105		highways_done++;
104	106		}
105	107
106	108		void add_highway_by_cities(int from, int to){
107	109		highway(from, to)->old = TRUE;
108	110		build_highway( highway(from, to) );
109	111		}
110	112
111	113		void initialize_highways(){
112	114		int from, to;
113	115		Highway *hw;
114	116
115	117		highways_count = 0;
116	118		for(to = 1; to < cities_count; to++){
117	119		for(from = 0; from < to; from++){
118	120		highways_count++;
119	121		hw = highway(from, to);
120	122
121	123		hw->to = to;
122	124		hw->old = FALSE;
123	125		hw->from = from;
124	126		hw->done = FALSE;
125	127		hw->distance = distance(from, to);
126	128		}
127	129		}
128	130		}
129	131
130	132		int compare_highways(const void highway_a, const void highway_b){
131	133		// if(((Highway*)highway_a)->done) return 1;
132	134		// if(((Highway*)highway_b)->done) return -1;
133	135		if(((Highway)highway_a)->distance > ((Highway)highway_b)->distance) return 1;
134	136		if(((Highway)highway_a)->distance < ((Highway)highway_b)->distance) return -1;
135	137		return 0;
136	138		}
137	139
138	140		void debug_highways(){
139	141		int i;
140	142		printf("\n\n");
141	143		for(i = 0; i < highways_count; i++){
142	144		printf("Highway: (%3d, %3d) %d %d %lf\n", highways[i].from, highways[i].to, highways[i].done, highways[i].old, highways[i].distance);
143	145		}
144	146		}
145	147
146	148		void kruskal(){
147	149		int i;
148	150		Highway *hw;
149	151		qsort(highways, highways_count, sizeof(Highway), compare_highways);
150	152		if(DEBUG) debug_highways();
151	153
152	154		for(i = 0; i < highways_count; i++){
153	155		if( !highways[i].done && !create_cicles(&highways[i]) ){
154	156		if(DEBUG) printf("(%3d,%3d)-(%3d,%3d)-(%d==%d, %d)\n", highways[i].from, highways[i].to, sets[highways[i].from], sets[highways[i].to], cities_connected, cities_count, sets_count);
155	157		build_highway(&highways[i]);
156	158		printf("%d %d\n", highways[i].from+1, highways[i].to+1);
157	159		if(ended()) break;
158	160		}
159	161		}
160	162		}
161	163
162	164		int main(){
163	165		int i, j, from, to;
164	166		int test_cases;
165	167
166	168		scanf("%d", &test_cases);
167	169
168	170		for(i = 0; i < test_cases; i++){
169	171		scanf("%d", &cities_count);
170	172		sets_count = 0;
	173	+	sets_luid = 0;
171	174		cities_connected = 0;
172	175		for(j = 0; j < cities_count; j++){
173	176		scanf("%d %d", &(cities[j].x), &(cities[j].y));
174	177		cities[j].connected = FALSE;
175	178		sets[j] = -1;
176	179		}
177	180
178	181		initialize_highways();
179	182		scanf("%d", &highways_done);
180	183		for(j = highways_done; j > 0; j--){
181	184		scanf("%d %d", &from, &to);
182	185		if(from == to){
183	186		highways_done--;
184	187		}else{
185	188		if(highway(from-1, to-1)->done){
186	189		highways_done--;
187	190		}else{
188	191		add_highway_by_cities(from-1, to-1);
189	192		}
190	193		}
191	194		}
192	195
193	196		// printf("(%d==%d, %d)\n", cities_connected, cities_count, sets_count);
194	197
195	198		if(ended() \|\| cities_count == 1){
196	199		printf("No new highways need\n");
197	200		}else{
198	201		if(DEBUG) debug_highways();
199	202		kruskal();
200	203		if(DEBUG) debug_highways();
201	204		}
202	205
203	206		if(i+1 < test_cases) printf("\n");
204	207		}
205	208
206	209		return 0;
207	210		}
208	211