제출 #13309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13309		heesub	비용 (KOI11_cost)	C++98	24 / 24	64 ms	4692 KiB

cost

#include <stdio.h>
#include <vector>
#include <algorithm>

#define MAX_V	100000
#define MAX_E	100000

class edge {
public:
	edge(int from, int to, int weight)
	{
		_from = from;
		_to = to;
		_weight = weight;
	}

	int _from;
	int _to;
	int _weight;
};

bool operator<(const edge& x, const edge& y)
{
	return x._weight > y._weight;
}

std::vector<edge> edges;

int uf[MAX_V + 1];
int rank[MAX_V + 1];
int adj[MAX_V + 1];

static int _find(int v1)
{
	int tmp = v1;

	while (v1 != uf[v1])
		v1 = uf[v1];

	uf[tmp] = v1;

	return v1;
}

static unsigned int _union(int v1, int v2)
{
	int ret = 0;
	int pv1 = _find(v1);
	int pv2 = _find(v2);

	/* already connected */
	if (pv1 == pv2) return ret;

	ret = adj[pv1] * adj[pv2];

	if (rank[pv1] > rank[pv2]) {
		uf[pv2] = pv1;
		adj[pv1] += adj[pv2];
	}
	else {
		uf[pv1] = pv2;
		adj[pv2] += adj[pv1];
		if (rank[pv1] == rank[pv2])
			rank[pv2]++;
	}

	return ret;
}

int main(void)
{
	int nr_vertices, nr_edges;
	unsigned long long sum = 0, total = 0;

	scanf("%d %d", &nr_vertices, &nr_edges);
	
	for (int i = 0; i < nr_edges; i++) {
		int from, to, weight;
		scanf("%d %d %d", &from, &to, &weight);
		edges.push_back(edge(from, to, weight));
		total += weight;
	}

	std::sort(edges.begin(), edges.end());

	/* initialize uf */
	for (int i = 1; i <= nr_vertices; i++) {
		uf[i] = i;
		adj[i] = rank[i] = 1;
	}

	for (std::vector<edge>::iterator iter = edges.begin(); iter != edges.end(); iter++) {
		sum += _union(iter->_from, iter->_to) * total;
		total -= iter->_weight;
	}

	printf("%llu\n", sum % 1000000000);

	return 0;
}

• Subtask 1: 4.8 / 4.8
• Subtask 2: 7.2 / 7.2
• Subtask 3: 12 / 12