http://acm.hdu.edu.cn/showproblem.php?pid=6141
题意：
求最大树形图。
思路：
把边的权值变为负值，那么这就是个最小树形图了，直接套模板就可以解决。
有个问题就是n结点的父亲结点的编号要尽量小，这里有个技巧可以用，权值编码，将所有边的权值都放大1000倍，对于和n相连的边，每条边在减去（n-u）的权值。这样就会去优先考虑编号小的边，而且因为权值最大为100，所以扩大1000是不会影响结果的。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pll;
const int inf = 0x3f3f3f3f;
const int maxn=+;
const int mod=1e9+; int n, m; struct node
{
int u,v,w;
}edge[*maxn]; int pre[maxn],id[maxn],use[maxn];
int in[maxn]; int mini_tree(int root,int n,int m)//分别是树根，节点数，边数，序号从1开始
{
int ans=;
int u;
while(true)
{
for(int i=;i<=n;i++) in[i]=inf;
for(int i=;i<=m;i++)
{
int u=edge[i].u;
int v=edge[i].v;
if(edge[i].w<in[v]&&u!=v)
{
in[v]=edge[i].w;
pre[v]=u;
}
}//找最小的入边
for(int i=;i<=n;i++)
{
if(i==root)continue;
ans+=in[i];//把边权加起来
if(in[i]==inf)//如果存在没有入弧的点则不存在最小树形图
return -;
}
memset(id,-,sizeof(id));
memset(use,-,sizeof(use));
int cnt=;
for(int i=;i<=n;i++)//枚举每个点，搜索找环
{
int v=i;
while(v!=root&&use[v]!=i&&id[v]==-)
{
use[v]=i;
v=pre[v];
}
if(v!=root&&id[v]==-)//当找到环的时候缩点编号
{
++cnt;
id[v]=cnt;
for(u=pre[v];u!=v;u=pre[u])
id[u]=cnt;
}
}
if(cnt==)//如果没有环结束程序
break;
for(int i=;i<=n;i++)//把余下的不在环里的点编号
if(id[i]==-)
id[i]=++cnt;
for(int i=;i<=m;i++)//建立新的图
{
int u=edge[i].u;
int v=edge[i].v;
edge[i].u=id[u];
edge[i].v=id[v];
if(edge[i].u!=edge[i].v)
edge[i].w-=in[v];
}
n=cnt;//更新节点数和根节点的编号
root=id[root];
}
return ans;
} int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
w*=-;
if(v==n) w-=(n-u);
edge[i].u=u, edge[i].v=v, edge[i].w=w;
}
int ans=mini_tree(,n,m);
printf("%d %d\n",-ans/,n-(-ans)%);
}
return ;
}