UVA 11183 最小树形图板子

UVA 11183

  • 有向图的最小生成树.
  • 朱刘算法板子
    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
    #include <iostream>
    #include <algorithm>
    #include <math.h>
    #include <string.h>
    using namespace std;
    const int edgemaxn = 4e4+5;
    const int maxn = 1e3+5;
    const int inf =  0x3f3f3f3f;

    struct node {
    	int u, v,w;
    }edge[edgemaxn];
    int pre[maxn], id[maxn], vis[maxn], n, m;
    int in[maxn];

    int mst(int root, int nn, int mm) {
    	int res = 0;
    	while (1) {
    		for (int i = 0; i < nn; i++) in[i] = inf; //每个点的最小入边初始化为inf
    		for (int i = 0; i < mm; i++) {
    			int u = edge[i].u, v = edge[i].v;
    			if (edge[i].w < in[v] && u != v) { //不是自环,初始化每个点的入边最小值,和上一个点
    				pre[v] = u;
    				in[v] = edge[i].w;
    			}
    		}
    		for (int i = 0; i < nn; i++) {
    			if (i == root) continue;
    			if (in[i] == inf) return -1; //如果有除去根节点的任何一点没有入边,那么构成不了最小生成树
    		}
    		int cnt = 0;
    		memset(id, -1, sizeof id); memset(vis, -1, sizeof vis);
    		in[root] = 0;
    		for (int i = 0; i < nn; i++) {//一直找每个点的前一个点,缩点、标记点来建立新图
    			res += in[i];//记录每个点的入边,就是有向图的最小生成树的值
    			int v = i;
    			//每个点一直寻找前一个点,看是否存在环，若不存在则会找到根节点
    			while (vis[v] != i && id[v] == -1 && v != root) {
    				vis[v] = i; v = pre[v];
    			}
    			if (v != root && id[v] == -1) {
    				for (int u = pre[v]; u != v; u = pre[u]) id[u] = cnt;
    				id[v] = cnt++;
    			}
    		}
    		if (cnt == 0) break;
    		//有的点没有新id,比如根节点
    		for (int i = 0; i < nn; i++) if (id[i] == -1) id[i] = cnt++;
    		for (int i = 0; i < mm; i++) {
    			int u = edge[i].u, v = edge[i].v;
    			edge[i].u = id[u];
    			edge[i].v = id[v];
    			if (id[u] != id[v]) edge[i].w -= in[v];
    		}
    		nn = cnt;
    		root = id[root];
    	}
    	return res;
    }
    int main() {
    //	freopen("a.txt","r",stdin);
    	int times; scanf("%d", &times);
    	for (int casei = 1; casei <= times; casei++) {
    		scanf("%d%d", &n, &m);
    		//for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
    		for (int i = 0; i < m; i++) { //m条有向边
    			int temp;
    			scanf("%d%d%d", &edge[i].u, &edge[i].v,&temp);
    			//edge[i].u--; edge[i].v--;
    			if (edge[i].u != edge[i].v) edge[i].w = temp;
    			else edge[i].w = inf;//2个顶点相同,自环的距离是无穷
    		}
    		int ans = mst(0, n, m);
    		if (ans == -1) printf("Case #%d: Possums!\n",casei);
    		else printf("Case #%d: %d\n",casei,ans);
    	}
    	return 0;
    }