HDU 2121 无定根最小树形图

HDU 2121

  • 题目给出有向图,求出最小生成树同时求出根节点.
  • 首先要会朱刘算法.将不定根构造成求定根,在求定根的朱刘算法板子上修改一下.

    方法

  1. 构造一个定根(0,此题点从1-n),该定根连接图中每一个点.并且权值是>原图所有边的权值和的任何值,我们取sum+1,求出来的 生成树的和-构造的边的和(sum+1)就是不定根的最小树形图的和,
  • 取>原图权值和的原因是让构造的跟到原图的每一个点的机会都相等,机会相等能让最后减去这条边时不影响原图的最小生成树
  • 比如:构造的边权值是0,那么这个构造的顶点永远都是新图的根节点.改变了题目让我求原图的生成树的初衷.
  • 如果最后求出来的ans大于sum,例如sum=30,然后我们+1保证机会相同,ans - 31(构造的边) >= 31(即>30),说明构造的跟有多个出边.即原图不能组成生成树,有的点到不了,只有通过新构造的图的边才能到达.
  • 因为每个图中节点编号不一样,记录边的编号ansroot来找到原图的起点.
    if (root == u) 即构造的图的根节点的出边,这条出边指向的点就是题目给出图的原点
    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
    #include <iostream>
    #include <algorithm>
    #include <math.h>
    #include <string.h>
    using namespace std;
    const int maxn = 1e3 + 5;
    const int inf = 0x3f3f3f3f;

    struct node {
    	int u, v, w,ansroot;
    }edge[10005];
    int pre[maxn], id[maxn], vis[maxn], n, m;
    int in[maxn], ansroot;
    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;
    				if (root == u) ansroot = i;
    			}
    		}
    		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);
    	while (scanf("%d%d", &n, &m) != EOF) {
    		//for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
    		int sum = 0;
    		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个顶点相同,自环的距离是无穷
    			sum += temp;
    		}
    		sum++;
    		for (int i = m; i < m + n; i++) {
    			edge[i].u = 0;
    			edge[i].v = i - m + 1;
    			edge[i].w = sum;
    		}
    		int ans = mst(0, n+1, m+n);
    		if (ans == -1 || ans - sum >= sum) printf("impossible\n");
    		else printf("%d %d\n", ans - sum, ansroot - m);
    		printf("\n");
    	}
    	return 0;
    }