题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2121
题目大意：
有n个点，有m条单向路，问这n个点组成最小树形图的最小花费。
解题思路：
1：构造虚根最小树形图
因为是不定根，所以我们可以假设一个虚拟根，分别与n个点都有一条权值为r的虚边，假如我们把r设的非常大的话，我们求出来的最小数形图去掉虚点和虚边就是最小树形图了，如果去掉虚点和虚边图形变得不连通了，那么说明这n个点不存在最小树形图，因为r非常大，并且不存在任何一条边替换掉r，使得图形连通。
2：不含虚拟点的最小树形图的根节点
因为在缩点的时候我们需要给每一个点进行从新编号，这样对于我们是很尴尬的，于是我们只能从边上下手咯，我们在每次对点进行从新编号的时候记录下虚拟节点的出边编号。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = ;
const int N = ;
const double Exp = 1e-;
const int INF = 0x3f3f3f3f; struct Edge
{
int u, v, w;
}; Edge edge[N];
int rt;
int directed_MST (int root, int n, int m)
{
int ans = , u, v, i;
int pre[maxn], pr[maxn], vis[maxn], id[maxn];
while (true)
{
for (i=; i<n; i++)
pre[i] = INF;
for (i=; i<m; i++)
{
u = edge[i].u;
v = edge[i].v;
if (pre[v]>edge[i].w && u!=v)
{
pre[v] = edge[i].w;
pr[v] = u;
if (u == root)
rt = i;
}
}
for (i=; i<n; i++)
{
if (i == root)
continue;
if (pre[i] == INF)
return -;
}
memset (vis, -, sizeof(vis));
memset (id, -, sizeof(id));
pre[root] = ;
int cru = ;
for (i=; i<n; i++)
{
ans += pre[i];
v = i;
while (vis[v]!=i && id[v]==- && v!=root)
{
vis[v] = i;
v = pr[v];
}
if (v!=root && id[v]==-)
{
for (u=pr[v]; u!=v; u=pr[u])
id[u] = cru;
id[u] = cru++;
}
}
if (cru == )
break;
for (i=; i<n; i++)
if (id[i] == -)
id[i] = cru++;
for (i=; i<m; i++)
{
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 -= pre[v];
}
n = cru;
root = id[root];
}
return ans;
}
int main ()
{
int n, m;
while (scanf ("%d %d", &n, &m) != EOF)
{
int r = ;
for (int i=; i<m; i++)
{
scanf ("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
r += edge[i].w;
}
r += ;
for (int i=; i<n; i++)
edge[i+m].u = n, edge[i+m].v = i, edge[i+m].w = r;
int num = directed_MST(n, n+, m+n);
if (num==- || num - r >= r)
printf ("impossible\n\n");
else
printf ("%d %d\n\n", num - r, rt - m);
}
return ;
}