思路来自
最小树形图模板用kuangbin的
/*HDU 6141 - I am your Father! [ 最小树形图 ] | 2017 Multi-University Training Contest 8题意： N个点M条边求最大树形图，还问权值最大的图中第N个点的父亲编号最小能是多少 N <= 1e3, M <= 1e4分析： 为了使第n个点的父亲编号最小，修改权值，将所有权值扩大1000倍 连向第N个节点的边再加上 n-其父亲的编号 的权值 这样答案就是 ans/1000 和 n-ans%1000*/#includeusing namespace std;#define LL long longconst LL INF = 1e18;const int N = 1e3+5;const int M = 1e4+5;struct Edge { int u, v; LL cost;} edge[M];int pre[N], id[N], visit[N];LL in[N];int zhuliu(int root, int n, int m, Edge edge[]){ LL res = 0; int u, v; while (1) { 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, -1, sizeof(id)); memset(visit, -1, sizeof(visit)); in[root] = 0; for (int i = 0; i < n; i++) { res += in[i]; v = i; while (visit[v] != i && id[v] == -1 && v != root) { visit[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 t, n, m;int main(){ scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d%d%lld", &edge[i].u, &edge[i].v, &edge[i].cost); edge[i].cost *= 1000; if (edge[i].v == n) edge[i].cost += n-edge[i].u; edge[i].cost *= -1; edge[i].u--; edge[i].v--; } LL ans = zhuliu(0, n, m, edge); ans = -ans; int fa = n - ans % 1000; ans /= 1000; printf("%lld %d\n", ans, fa); }}