修路方案（nyoj），修路方案nyoj

修路方案（nyoj），修路方案nyoj

算法：次小生成樹

描述

南將軍率領著許多部隊，它們分別駐扎在N個不同的城市裡，這些城市分別編號1~N，由於交通不太便利，南將軍准備修路。

現在已經知道哪些城市之間可以修路，如果修路，花費是多少。

現在，軍師小工已經找到了一種修路的方案，能夠使各個城市都聯通起來，而且花費最少。

但是，南將軍說，這個修路方案所拼成的圖案很不吉利，想讓小工計算一下是否存在另外一種方案花費和剛才的方案一樣，現在你來幫小工寫一個程序算一下吧。

輸入

第一行輸入一個整數T(1<T<20)，表示測試數據的組數
每組測試數據的第一行是兩個整數V,E，(3<V<500,10<E<200000)分別表示城市的個數和城市之間路的條數。數據保證所有的城市都有路相連。
隨後的E行，每行有三個數字A B L，表示A號城市與B號城市之間修路花費為L。

輸出

對於每組測試數據輸出Yes或No（如果存在兩種以上的最小花費方案則輸出Yes,如果最小花費的方案只有一種，則輸出No)

樣例輸入

2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

樣例輸出

No
Yes

代碼：

#include <iostream>
  #include <algorithm>
  #include <cstring>
  #include <iomanip>
  #include <string>
  #include <stdio.h>
  using namespace std; 
  int pre[505],m,n;
  struct dot
  {
        int x,y,val,step;
  } node[200005];
  int cmp(dot a1,dot a2)
  {return a1.val<a2.val;}
  void inct()
  {
      for(int i=1;i<=500;i++)
      pre[i]=i;
  }
  int find(int ax)
  {
      while(ax!=pre[ax]) ax=pre[ax];
      return ax;
  }
  int check(int w)
  {
      int sum=0;
      for(int i=0;i<m;i++)
      {
          if(i!=w)
          {
              int fx=find(node[i].x);
              int fy=find(node[i].y);
              if(fx!=fy)
              {
                  sum+=node[i].val;
                pre[fy]=fx; 
            }
        }
    }
    int s=find(1);
    for(int i=2;i<=n;i++)
        if(find(i)!=s) return -1;
    return sum;
  }
  int main()
  {
      int i,j,k,q,p,T,mmin;
      cin>>T;
      while(T--)
      {   
          inct();
          cin>>n>>m;
          for(i=0;i<m;i++)
          {
              cin>>node[i].x>>node[i].y>>node[i].val;
              node[i].step=0;
        }
        sort(node,node+m,cmp);
        mmin=0;
        for(i=0;i<m;i++)
        {
            int fx=find(node[i].x);
            int fy=find(node[i].y);
            if(fx!=fy)
            {
                mmin+=node[i].val;
                pre[fy]=fx;
                node[i].step=1;//標記此邊最小生成樹用過； 
            }
        }
        int flag=0;
        for(i=0;i<m;i++)
        {
            if(node[i].step)
            {
                inct();
                int ans=check(i);
                if(ans==mmin)
                {
                    flag=1;
                    break;
                }
            }
        }
        if(flag) printf("Yes\n"); 
        else printf("No\n");
    }
    return 0;
  }