06月
13

POJ_1679 The Unique MST

发表于 • 本文总阅读数 次
字数统计: 484

题目

  http://poj.org/problem?id=1679

题意

  给出一张无向图，问图的最小生成数是否唯一，不唯一的话输出Not Unique!，否则输出最小生成树的边权和。

题目解析

  算出图的最小生成树，然后算出次小生成数，判断一下是否相等。（第一次写次小生成树，bug改了好久(T﹏T)！）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* http://poj.org/problem?id=1679 */
/* AC 0MS 412K */
#include <stdio.h>
#include <string.h>

const int MAX_N = 100 + 5;
const int INF = 0x1f1f1f1f;

int n, m;
int mp[MAX_N][MAX_N];
int mst[MAX_N];
int maxd[MAX_N][MAX_N];

int prim()
{
	int i, j, k, min, ans;
	int dist[MAX_N];

	for(i = 1; i <= n; i++)
	{
		dist[i] = mp[1][i];
		mst[i] = 1;
	}
	dist[1] = -1;
	
	ans = 0;
	for(i = 2; i <= n; i++)
	{
		min = INF;
		for(j = 2; j <= n; j++)
		{
			if(dist[j] != -1 && min > dist[j])
			{
				min = dist[j];
				k = j;
			}
		}
		if(min == INF)
		{
			return -1;
		}
		ans += dist[k];
		dist[k] = -1;
		for(j = 1; j <= n; j++)
		{
			if(dist[j] != -1 && dist[j] > mp[k][j])
			{
				dist[j] = mp[k][j];
				mst[j] = k;
			}
			if(dist[j] == -1)
			{
				int pre = mst[k];
				maxd[j][k] = (maxd[j][pre] > mp[pre][k]) ? maxd[j][pre] : mp[pre][k];
				maxd[k][j] = maxd[j][k];
			}
		}
	}
	return ans;
}

int sec_mst(int mst_l)
{
	int i, j, ans;

	ans = INF;
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
		{
			if(i == j || mp[i][j] == INF || mst[i] == j || mst[j] == i)
			{
				continue;
			}
			if(ans > mst_l + mp[i][j] - maxd[i][j])
			{
				ans = mst_l + mp[i][j] - maxd[i][j];
			}
		}
	}
	if(ans == INF)
	{
		return -1;
	}
	else
	{
		return ans;
	}
}

int main()
{
	int t, i, x, y, w, mst_l;

	scanf("%d", &t);
	while(t--)
	{
		scanf("%d %d", &n, &m);
		memset(mp, 0x1f, sizeof(mp));
		memset(maxd, 0, sizeof(maxd));
		for(i = 0; i <= n; i++)
		{
			mp[i][i] = 0;
		}
		for(i = 0; i < m; i++)
		{
			scanf("%d %d %d", &x, &y, &w);
			if(mp[x][y] > w)
			{
				mp[x][y] = w;
				mp[y][x] = w;
			}
		}

		mst_l = prim();
		if(mst_l < 0 || mst_l == sec_mst(mst_l))
		{
			printf("Not Unique!\n");
		}
		else
		{
			printf("%d\n", mst_l);
		}
	}
	return 0;
}
分享到：
0%