Posted in Kruskal

POJ 2349

8/8/2017
Problem: http://poj.org/problem?id=2349
Solution: The answer is just the length of the k-th largest edge in the MST.

#include<cstdio>
#include<iostream> 
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

struct point{
	int x, y;
	point(int xx, int yy):x(xx), y(yy){}
	point(){}
};

struct edge{
	int i, j;
	double w;
	edge(int ii, int jj, double ww):i(ii), j(jj), w(ww){}
	edge(){}
};

point p[5005];
edge e[251010];
int parent[5005];

double dist(int x1, int y1, int x2, int y2) {
	return sqrt((double)(x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

bool cmp(edge a, edge b) {
	return a.w < b.w;
}

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		parent[a] = find(parent[a]);
		return parent[a];
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p2] = p1;
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		int s, n;
		cin >> s >> n;
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		} 
		for (int i = 1; i <= n; i++) {
			cin >> p[i].x >> p[i].y;
		} 
		int cnt = 0;
		for (int i = 1; i < n; i++) {
			for (int j = i + 1; j <= n; j++) {
				double tmp = dist(p[i].x, p[i].y, p[j].x, p[j].y);
				e[++cnt] = edge(i, j, tmp);
				e[++cnt] = edge(j, i, tmp);
			}
		}
		int node = 0;
		sort(e + 1, e + cnt + 1, cmp);
		for (int i = 1; i <= cnt; i++) {
			if (find(e[i].i) != find(e[i].j)) {
				merge(e[i].i, e[i].j);
				node++;
				if (node == n - s) {
					printf("%0.2f\n", e[i].w);
					break;
				}
			}
		}
	}
	return 0;
}
Posted in Kruskal

POJ 1258 Agri-Net

8/8/2017
Problem: http://poj.org/problem?id=1258
Solution: I used Kruskal but Prim is the same. Nothing noteworthy.


#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> parent;

struct Edge{
	int s, e, w;
	Edge(int ss, int ee, int ww):s(ss), e(ee), w(ww){}
};

vector<Edge> edge;

bool operator<(Edge a, Edge b) {
	return a.w < b.w;
}

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (find(p1) != find(p2)) {
		parent[p2] = p1;
	}
}

int main() {
	int n;
	while (cin >> n) {
		parent.clear();
		edge.clear();
		for (int i = 0; i <= n; i++) {
			parent.push_back(i);
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				int w;
				cin >> w;
				edge.push_back(Edge(i, j, w));
			}
		}
		sort(edge.begin(), edge.end());
		int node = 0;
		int len = 0;
		for (int i = 0; i < edge.size(); i++) {
			if (find(edge[i].s) != find(edge[i].e)) {
				merge(edge[i].s, edge[i].e);
				node++;
				len += edge[i].w;
			}
			if (node == n - 1) {
				break;
			}
		}
		cout << len << endl;		
	}
	return 0;
}