链接：http://acm.hdu.edu.cn/showproblem.php?pid=2121
题意：n个顶点，m条边，求从某一点起建立有向图最小生成树并且花费最小，输出最小花费和根节点下标。
思路：这道题根是不确定的，我们可以先假设一个根，从这个根出发到任何一点的距离（sum）都比原图总权值还大，这样保证了虚拟的边不会是最小入边，也为之后判断是否生成了最小树形图提供方便，从这个点开始建立最小树形图，最后生成出一个结果，很显然虚拟的根只有一条出边，并且出边连接的点就是真实的根。
最后得到的最小树形图权值，减去虚拟边的权值sum，如果结果大于等于sum，说明虚拟顶点的出边不止一条，也即如果不靠这个虚拟顶点原图无法构成最小树形图，这是最小树形图的另一个判断条件。
至于真实的根，找到某点的最小入边，如果出边的点是虚拟根，则这个点就是真实根，但是我们不能直接记录这个顶点，因为这个顶点可能是缩点后的点，所以我们记录边的编号，因为虚拟边的编号是从m开始增加n条边的，最后用记录的边的编号减去m就是真实根的下标。
/*
最小树形图图模版-朱刘算法
模版说明：点标号必须0-(N-1)
必须去除到自身的点（到自身的边的边权赋无限大）
*/
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 50100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define seed 131
#define mod 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct node{
int u,v;
int dis;
}edge[20100];
int pre[1010],ID[1010],vis[1010];
int n,m;
int In[1010];
int ansp;
int Directed_MST(int root,int NV,int NE) {
int ret = 0;
while(true) {
//1.找最小入边
for(int i=0;i<NV;i++) In[i] = INF;
for(int i=0;i<NE;i++){
int u = edge[i].u;
int v = edge[i].v;
if(edge[i].dis < In[v] && u != v) {
pre[v] = u;
In[v] = edge[i].dis;
if(u==root) ansp = i; //实际上应该等于v，但是v有可能是缩点，所以等于i，之后再减去m就是顶点编号
}
}
for(int i=0;i<NV;i++) {
if(i == root) continue;
if(In[i] == INF) return -1;//除了根以外有点没有入边,则根无法到达它
}
//2.找环
int cntnode = 0;
memset(ID,-1,sizeof(ID));
memset(vis,-1,sizeof(vis));
In[root] = 0;
for(int i=0;i<NV;i++) {//标记每个环
ret += 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] = cntnode;
}
ID[v] = cntnode ++;
}
}
if(cntnode == 0) break;//无环
for(int i=0;i<NV;i++) if(ID[i] == -1) {
ID[i] = cntnode ++;
}
//3.缩点,重新标记
for(int i=0;i<NE;i++) {
int 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].dis -= In[v];
}
}
NV = cntnode;
root = ID[root];
}
return ret;
}
int main(){
int i,j,a,b,c;
double temp;
while(scanf("%d%d",&n,&m)!=EOF){
int x = m;
int sum = 0;
for(i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
edge[i].u = a + 1;
edge[i].v = b + 1;
edge[i].dis = c;
sum += c;
}
sum++;
for(i=m;i<m+n;i++){
edge[i].u = 0;
edge[i].v = i - m + 1;
edge[i].dis = sum;
}
int ans = Directed_MST(0,n+1,m+n);
if(ans==-1||ans-sum>=sum) puts("impossible");
else printf("%d %d\n",ans-sum,ansp-x);
puts("");
}
return 0;
}
HDUOJ--2121--Ice_cream’s world II【朱刘算法】不定根最小树形图,布布扣,bubuko.com
HDUOJ--2121--Ice_cream’s world II【朱刘算法】不定根最小树形图
原文：http://blog.csdn.net/zzzz40/article/details/38470711