「HDU-6141」I am your Father!(最小树形图)

发表于 | 分类于 ，

「HDU-6141」I am your Father!
求最大树形图，并最小化点n​父亲结点的编号

题意

给定一个有向图，求出以1为根的最大树形图，如果有多个，则使$n$结点的父亲节点编号最小。输出边权和$W$和点$n$的父亲节点。

思路

对于$W$，可以直接对边权取负，跑一遍朱刘算法。

为使点$n$的父亲节点编号最小，需要对连向点$n$的边进行加权操作，并且需要保证加权后的权值不会影响原图。

对于原图上的边，对边权*1000，而加权操作加上的权值为起始点$u$的编号(不超过1000)，即可保证在不影响原结果的情况下，求出父节点编号最小的解。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=1000;
const int maxm=10000;

struct Edge{int u,v,cost; } edge[maxm];

int pre[maxn], id[maxn], vis[maxn], in[maxn];

int zhuliu(int root, int n, int m)
{
	int res=0, u, v;
	for(;;)
	{
		for(int i=0; i<n; i++) in[i] = INF;
		for(int i=0; i<m; i++) if(edge[i].u != edge[i].v && edge[i].cost < in[edge[i].v])
		{
			pre[edge[i].v] = edge[i].u;
			in[edge[i].v] = edge[i].cost;
		}
		for(int i=0; i<n; i++) if(i != root && in[i] ==INF) return -1;
		int tn=0;
		memset(id, 0xff, sizeof id);
		memset(vis, 0xff, sizeof vis);
		in[root] = 0;
		for(int i=0; i<n;i++)
		{
			res += in[i];
			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] = tn;
				id[v] = tn++;
			}
		}
		if(tn == 0) break;
		for(int i=0; i<n; i++) if(id[i] == -1) id[i] = tn++;
		for(int i=0; i<m;)
		{
			v = edge[i].v;
			edge[i].u = id[edge[i].u];
			edge[i].v = id[edge[i].v];
			if(edge[i].u != edge[i].v) edge[i++].cost -= in[v];
			else swap(edge[i], edge[--m]);
		}
		n = tn;
		root = id[root];
	}
	return res;
}

int main()
{
    int t, n, m, u, v, w;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d",&n, &m);
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d",&edge[i].u, &edge[i].v, &edge[i].cost);
            edge[i].u--;
            edge[i].v--;
            edge[i].cost = -edge[i].cost * 1000;
            if(edge[i].v == n - 1) edge[i].cost += edge[i].u;
        }
        int res = -zhuliu(0, n, m);
        int ans = (res + 999) / 1000, pos = ans * 1000 - res;
        printf("%d %d\n", ans, pos + 1);
    }
    return 0;
}