最小树形图，却不知道怎么求n的父亲，直到看到一篇大佬题解；http://blog.csdn.net/mr__kid/article/details/77371066
分析：首先，这里求的是最大树形图，我们可以将所有边的权值乘以-1，然后根据最小树形图算法，求出最小树形图的权值和，再乘回-1就是该有向图的最大树形图权值。但是这样是求不出n号节点的最小字典序父亲节点的，朱刘算法中会将节点序号打乱，也就是我们会丢失节点序号，那这里怎么办呢？这里就用到了权值编码。我们可以思考，既然朱刘算法会将节点序号改变，那么什么是不变的呢？那肯定就是进入n号节点的最小边，如果我们将n号节点的父亲节点信息存到边中，然后再还原回来，不就可以了？这就是权值编码的神奇之处了。这里的操作是，我们将所有的权值都乘以-n，为什么是乘以-n，而不是乘以别的数呢？这里做个记号#1，先不讨论。然后当存在某条边（u，v，w），其中v是n号节点，那么我就将这条边的权值w+=u（这里的w已经进行过乘以-n的操作了。），那么这里问题来了，我这样w+=u，会不会改变节点到达n点权值的相对大小呢？正常情况下是会的，但是这里我们可以提前避开这个问题，这里做个记号#2，先不讨论。然后，当我们根据以上操作处理完所有的权值以及到达n的权值之后，就可以直接跑最小树形图。当我们做完最小树形图之后，会得到一个负数ans1，这个ans1=-n*wi+u，其中wi表示选中边初始的权值和，u表示进入n的父亲节点（神奇吧？），那么此时我们经过乘以ans1*-1，会得到ans2=n*wi-u，这时，我们可以很明显的发现，我们所求的最大树形图权值就是所有wi的和，n的最小字典序父亲节点就是u。到了这一步，我们的工作就是处理ans2。对于最大树形图的权值，我们不能直接（ans2=n*wi-u）/n，这里-u的做操作会使最终结果少1，因此，我们这样操作（ans2+n-1）/n=（n*wi-u+n-1）/n，这里0<-u+n-1<n，因此最大树形图的权值cost=（ans2+n-1）/n，求出，权值，我们需要将u提取出来。根据上边的结论，ans1=-n*wi+u，然后cost=wi，那么我们可以很快得出u=cost*n+ans1，然后事情就完美解决啦~PS：注意这里的wi都是指选中边的初始权值和而不是一条边
这里来解释一下#1和#2操作。首先，#2出现的问题是在#1的基础上完美避开的，在#2中，如果两条边的权值w（负数）相同，我们通过加上u值，这里假设u1<u2，那么w+u1<w+u2，然后u1显然是我们需要找的父亲节点，w+u1这条边也就是我们要找的。当两条边的权值w1，w2（已经乘-n变成负数）不同的时候，对于u1，u2，必然有w1+u1和为w2+u2，其中必然存在0<|u1-u2|<n，此时我们假设w1<w2，那么显然w1比w2更优，那么我们如何使w1+u1<w2+u2成立呢？？此时我们知道w1!=w2，那么必然有|w2-w1|≥n，这里我们的w1和w2已经扩大了-n倍，那么也就是说，在w1<w2的情况下，必然存在w2-w1≥n，那么此时证明不等式w2+u2>w1+u1等价于证明w2-w1>u1-u2，由于w2-w1≥n，n>|u1-u2|，
也就是w2-w1>u1-u2在（权值*-n）的情况下始终成立，也就是我们不会丢失最优解！！也就是说，只要我们乘以比-n小的任何数，都可以保持最优解不变。然后这道题就解决了。
以上粘贴大佬分析，下面是自己A的代码：
#include <cstdio> #include <cstring> #include<algorithm> using namespace std; const int MAXNODE = 1010; const int MAXEDGE = 10010; typedef int Type; const Type INF = 0x3f3f3f3f; struct Edge { int u, v; Type dis; Edge() {} Edge(int u, int v, Type dis): u(u), v(v), dis(dis) {} }; struct Directed_MT { int n, m; Edge edges[MAXEDGE]; int vis[MAXNODE]; int pre[MAXNODE]; int id[MAXNODE]; Type in[MAXNODE]; void init(int n) { this->n = n; m = 0; } void AddEdge(int u, int v, Type dis) { edges[m++] = Edge(u, v, dis); } Type DirMt(int root) { Type ans = 0; while (1) { for (int i = 0; i < n; i++) in[i] = INF; for (int i = 0; i < m; i++) { int u = edges[i].u; int v = edges[i].v; if (edges[i].dis < in[v] && u != v) { in[v] = edges[i].dis; pre[v] = u; } } for (int i = 0; i < n; 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 < n; i++) { ans += 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; for (int i = 0; i < n; i++) if (id[i] == -1) id[i] = cnt++; for(int i = 0;i < m;) { int v = edges[i].v; edges[i].u = id[edges[i].u]; edges[i].v = id[edges[i].v]; if(edges[i].u != edges[i].v) edges[i++].dis -= in[v]; else swap(edges[i],edges[--m]); } n = cnt; root = id[root]; } return ans; } }MT; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int T;scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); MT.init(n); while(m--) { int x,y,w; scanf("%d%d%d",&x,&y,&w); if(y==n)w=-1000*w+x; else w*=-1000; MT.AddEdge(x-1,y-1,w); } int ans= MT.DirMt(0); printf("%d %d ", (-ans+999)/1000, (-ans+999)/1000*1000+ans); } return 0; }