UVA 10600 prim次小生成树

UVA 10600

  • 次小生成树prim板子
  • 代码第44行.发现更新最小生成树中的maxdist[][](2点之间的最大边),不能更新point,也就是刚加入生成树中的点,这样就会更新自环，变成了dist[point],而自环应该是0
    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
    #include <iostream>
    #include <algorithm>
    #include <string.h>

    using namespace std;
    const int maxn = 1e3 + 5;
    const int INF = 0x3f3f3f3f;

    bool vis[maxn];
    int dist[maxn];
    int e[maxn][maxn];
    int n, m;
    int sum;
    bool use[maxn][maxn];
    int maxdist[maxn][maxn];
    int pre[maxn];

    int prim() {
    	sum = 0;
    	memset(vis, 0, sizeof vis);
    	memset(use, 0, sizeof use);
    	memset(maxdist, 0, sizeof maxdist);
    	vis[1] = 1; //点1加入到最小生成树中
    	for (int i = 1; i <= n; i++) {
    		dist[i] = e[1][i];
    		pre[i] = 1;
    	}
    	dist[1] = 0;
    	pre[1] = 0;

    	for (int i = 1; i < n; i++) {
    		int minn = INF;
    		int point = INF;
    		for (int j = 1; j <= n; j++) {
    			if (!vis[j] && dist[j] < minn) {
    				point = j;
    				minn = dist[j];
    			}
    		}
    		vis[point] = 1;
    		sum += minn;
    		use[point][pre[point]] = use[pre[point]][point] = 1; //标记在树的点
    		for (int j = 1; j <= n; j++) { //更新每个点到树的距离
    			if (vis[j] && j!=point) // j==point 更新的就是自环,自环应该为0,而这里会变成dist[point];  
    				maxdist[j][point] = maxdist[point][j] = max(maxdist[j][pre[point]], dist[point]);
    			if (!vis[j] && e[point][j] < dist[j]) {
    				dist[j] = e[point][j];
    				pre[j] = point; //既然更新了路径,也更新该点指向的上一个点
    			}
    		}
    	}
    	return sum;
    }
    int superprim() {
    	int ans = INF;
    	for (int i = 1; i <= n; i++) { //枚举所有的
    		for (int j = 1; j <= n; j++) {
    			if (!use[i][j] && e[i][j] != INF) {
    				ans = min(sum + e[i][j] - maxdist[i][j], ans);
    //				printf("ans=%d e[%d][%d]=%d maxdist[%d][%d]=%d\n",ans,i,j,e[i][j],i,j,maxdist[i][j]);
    			}
    		}
    	}
    	return ans;
    }

    int main() {
    //	freopen("a.txt", "r", stdin);
    	int times; cin >> times;
    	while (times--) {
    		scanf("%d%d",&n,&m);
    		memset(e, 0x3f, sizeof e);
    		for (int i = 1; i <= m; i++) {
    			int u, v, w; scanf("%d%d%d",&u,&v,&w);
    			e[u][v] = e[v][u] =  min(e[u][v],w);
    		}
    		prim(); int ans = superprim();
    		printf("%d %d\n",sum, ans);
    	}
    	return 0;
    }