URAL 1416. Confidential

Author: 2015-08-28

ACM

, , ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1416

1416. Confidential

Time limit: 2.0 second
Memory limit: 64 MB
Zaphod Beeblebrox — President of the Imperial Galactic Government. And by chance he is an owner of enterprises that trade in secondhand pens. This is a complicated highly protable and highly competitive business. If you want to stay a leader you are to minimize your expenses all the time. And the presedent’s high post helps in those aairs. But he is to keep this business in secret. As a president Zaphod has access to the top secret and important information an exact value of power loss in the hyperspace transition between the planets. Of course, this information is very useful to his company. Zaphod is to choose the minimal possible set of trans-planet passages so that he could pass from any planet to any other one via those passages and their total cost would be minimal. The task won’t be complicated if Zaphod was not to keep in secret that he helps his company with the secret information. Thus, Zaphod decided to find not the cheapest passages set but the next one. As a real businessman he wants to estimate the value of his conspiracy expenses.

Input

The first line contains integers n and m that are a number of planets in the Galaxy and an amount of passages between them (2 ≤ n ≤ 500). The next m lines contain integers ai, bi and wi that are the numbers of the planets connected with the passage and the transition cost (1 ≤ ai, bi ≤ n; 0 ≤ wi ≤ 1000). If an A to B transition is possible then a B to A transition is possible too, and the cost of these transitions are equal. There is no more than one passage between any two planets. One can reach any planet from any other planet via some chain of these passages.

Output

You should find two different sets of transitions with the minimal possible cost and output theirs costs. Print the minimal possible cost first. If any of those sets of transitions does not exist denote it’s cost by −1.

Samples

input output 
4 6
1 2 2
2 3 2
3 4 2
4 1 2
1 3 1
2 4 1

Cost: 4
Cost: 4

3 2
1 2 2
2 3 2

Cost: 4
Cost: -1
Problem Author: Den Raskovalov
Problem Source: The Ural State University Championship, October 29, 2005

2. 思路

给出若干星球间的通道和旅行消耗，求连通所有星球的通道的最少消耗和次少消耗。

求最小生成树和次小生成树。在求最小生成树的过程中，使用二维数组cand[i][j] 记录最小生成树中，从节点i到节点j的路径上权值最大边的权值。求得最小生成树后，遍历所有不在最小生成树里面的边(i, j)，边(i, j)可以用于替换最小生成树中权值为cand[i][j] 的边，由此带来的额外消耗为边(i, j)的权值减去cand[i][j] 。使得此额外消耗最小的边(i, j)，替换最小生成树中权值为cand[i][j] 的边后，即得到次小生成树，此额外消耗最小值即为次小生成树与最小生成树间的差距。

3.代码

#include <stdio.h>

#define MAX_N 501
#define MAX_W 1001

typedef short Cost[MAX_N][MAX_N];

void solveE9b_Confidential();
void inputCost(Cost cost, int n, int passageNum);
void init(Cost cost, int n, int value);

int main() {
	solveE9b_Confidential();
}

Cost cost, cand;
int connectedNum;
// unsigned char connected[MAX_N];
short connected[MAX_N];
bool isConnected[MAX_N];
void solveE9b_Confidential() {
	int n, m;
	scanf("%d %d", &n, &m);

	inputCost(cost, n, m);

	init(cand, n, 0);
	connected[connectedNum++] = 1;
	isConnected[1] = true;

	int totalCost = 0;
	while (connectedNum < n) {
		int minCost = MAX_W, minCostId, minCostConnectedId;
		for (int i = 1; i <= n; ++i) {
			if (!isConnected[i]) {
				for (int j = 0; j < connectedNum; ++j) {
					if (cost[i][connected[j]] < minCost) {
						minCost = cost[i][connected[j]];
						minCostId = i;
						minCostConnectedId = connected[j];
					}
				}
			}
		}

		for (int i = 0; i < connectedNum; ++i) {
			cand[connected[i]][minCostId] = cand[connected[i]][minCostConnectedId] > minCost ? cand[connected[i]][minCostConnectedId] : minCost;
			cand[minCostId][connected[i]] = cand[connected[i]][minCostId];
		}
		
		totalCost += minCost;
		connected[connectedNum++] = minCostId;
		isConnected[minCostId] = true;
		cost[minCostId][minCostConnectedId] = MAX_W;
		cost[minCostConnectedId][minCostId] = MAX_W;
	}

	int extraCost, minExtraCost = MAX_W;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if ((i != j) && (cost[i][j] < MAX_W)) {
				extraCost = cost[i][j] - cand[i][j];
				if (extraCost < minExtraCost) {
					minExtraCost = extraCost;
				}
			}
		}
	}
	int newTotalCost = minExtraCost == MAX_W ? -1 : (totalCost + minExtraCost);

	printf("Cost: %d\n", totalCost);
	printf("Cost: %d\n", newTotalCost);
}

void inputCost(Cost cost, int n, int passageNum) {
	init(cost, n, MAX_W);

	int a, b, w;
	for (int i = 0; i < passageNum; ++i) {
		scanf("%d %d %d", &a, &b, &w);
		cost[a][b] = w;
		cost[b][a] = w;
	}
}

void init(Cost cost, int n, int value) {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cost[i][j] = value;
		}
	}
}