HDU 2121 Ice_cream’s world II(不定根最小树形图) - c++编程基础

int n; // 结点个数
int size; // 边的数量
int pre[VN]; // 权值最小的前驱边
int id[VN];
int vis[VN]; // 是在环中还是在环外
};

Directed_MSTG;

int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
G.init(n+1);
int Max = 0;
for(int i=0; i int a,b;
int c;
scanf("%d%d%d",&a,&b,&c);
if(a==b)continue;

Max += c;
G.insert(a+1,b+1,c);
}
++Max;
// 把n+1设置为虚拟根结点
for(int i=m; i G.insert(n+1, i-m+1, Max); // 注意虚拟结点n+1与i的关系，当i>m之后，依次从虚拟根结点n+1出发
// 到达1,2,...,n.利用这个关系，当i>m时利用位置就可以确定m+1与其它结点的关系
// 后面要用这个关系输出根结点
}

int ans = G.directed_mst(n+1);

if(ans==-1 || ans-Max>=Max)puts("impossible");
else printf("%d %d\n", ans-Max, ans_root-m);
puts("");
}
return 0;
}

HDU 2121 Ice_cream’s world II(不定根最小树形图)(二)