UVA 11183(最小ツリー図)

一番小さい木のテンプレートの問題で、勉強しました.
http://hi.baidu.com/lydrainbowcat/item/5fbae3fb9c159c5ec8f33753
以下はこのブログから転送します.
ルートノードはすでに知っていて、この有向図の最小の木の形の図を求めます.最小ツリー図は、ルートノードが図中のすべてのノードに到達し、選択したエッジのエッジ重みと最小化を可能にするために、図の最小生成ツリーである.
テーマアルゴリズム:朱-劉アルゴリズム(すなわち中国人の朱永津と劉振宏が共同で発明したアルゴリズム).
アルゴリズムの手順は以下の通りです:(本稿では証明しません.以下に示す私が自分で描いた図を参考にすれば理解できます)
1.図の連通性を判断し、連通さなければ直接解がない、そうでなければ必ず解がある.
2.ルートノード以外のすべての点に対して1つの重み値が最も小さい入辺を選択し、pre配列で前駆体を記録し、f配列で選択した辺長を記録し、選択した辺権とtempを記録すると仮定する.
3.選択したエッジがループを構成しているか否かを判断し、なければ直接ans+=tempとしてansを出力し、あれば次の操作を行う.
4.このリングに縮点操作を施し、そのリングに点V 1,V 2…Vi……Vnがあり、縮成した点をnodeとする ,リングにないすべての点Pについて、以下の変更を行います.
(1) 点Pからnodeまでの距離はmin{a[p,Vi]-f[Vi]}(aはエッジセット配列)
 (2)点nodeからpまでの距離はmin{a[Vi,p]}
操作(1)の理解:まずリング上のすべてのエッジが選択されていると仮定し,次にあるエッジを選択してそのリングに入ると,進入点と進入点の前駆者の間のエッジ,すなわちF[進入点]を切断できるので,直接a[p,node]をmin{a[p,Vi]−f[Vi]}に割り当てることに等価である.
特に注意:本題には自環があり、事前に削除することができます.それは役に立たないからです.

#include
#include
#include
using namespace std;
const int maxn = 1005;
const int maxm = 40005;
const int inf = 0x3f3f3f3f;
struct node
{
    int from;
    int v;
    int len;
}edge[maxm];
int in[maxn],pre[maxn],id[maxn],vis[maxn];
int dir_mst(int root,int n,int m)
{
    int ans=0;
    while(1)
    {
        //           
        /*memset(in,inf,sizeof(in)); //      ！*/
        for(int i=0;i