poj 1679 The Unique MST 最小生成樹

poj 1679 The Unique MST 最小生成樹

題意：給一個無向圖，問最小生成樹是否唯一，如果唯一就輸出最小生成樹的所有邊的權值的和，如果不唯一，那麼就輸出Not Unique!

思路：在用prime算法求最小生成樹的過程中，在找到權值最小的一個節點之後，先判斷一下，這個節點的權值是否可以由好幾條路徑求得，並且權值都等於當前權值，如果是的話，那麼最小生成樹就不唯一。那麼如何判斷呢？可以用一個flag數組標記，0代表這個點得到當前權值的路徑唯一，1代表不唯一，初始化全為0。我們在用一個已找到的權值最小的節點i來更新其他點的權值的時候，如果發現某個點的現在的權值和i點到這個點的距離相等，那麼就說明這個點最少可以由兩條路徑來得到當前的這個最小值，就把他標記為1，如果這個點的權值比i點到它的距離要小，那麼就更行這個點的權值，並把flag標記為0，因為當前的這個最小值只能由i點得到，是唯一的，剩下的就是一個簡單的最小生成樹問題了。

#include
#include
#include
using namespace std;

const int maxn=110;
struct Side{
    int to,v,next;
}side[2*maxn*maxn];
int head[maxn],top;
int dis[maxn];
int n,m;
bool vis[maxn],flag[maxn];

void init(){
    memset(head,-1,sizeof(head));
    top=0;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f3f,sizeof(dis));
    memset(flag,0,sizeof(flag));
}

void addside(int a,int b,int c){
    side[top]=(Side){b,c,head[a]};
    head[a]=top++;
    side[top]=(Side){a,c,head[b]};
    head[b]=top++;
}

bool prime(){
    vis[1]=1;
    dis[1]=0;
    for(int i=head[1];i!=-1;i=side[i].next){
        dis[side[i].to]=side[i].v;
    }
    for(int i=0;iv){
                flag[to]=0;
                dis[to]=v;
            }
            else if(dis[to]==v)
                flag[to]=1;
        }
    }
    return 1;
}

int main()
{
    int cas;
    cin>>cas;
    while(cas--){
        init();
        cin>>n>>m;
        int a,b,c;
        for(int i=0;i