次小生成树 UVA --- 10462

题意就是判断是否存在最小生成树,如果存在,那又是否有次小生成树,有的话输出其值,否则按题意输出.
AC代码: (第一次过的时候时间达到了710ms,我嫌太长了,看那些都是10ms过的,于是不断的改,终于还是10ms也过了,哈哈,vector真的很好用!!!)

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<functional>
#include<vector>
#include<stack>
#include<map>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
#define mod 1000000007
using namespace std;
const int maxn = 2005;
const int inf = 1e9;
int cas=1;
int pre[maxn];
int n,m;
vector<int>used;   //申请一个动态数组保存第一次最小生成树用了哪些边. 用数组也行,但是vector更快! 所以多利用它吧.
struct node{ int u,v,w;} s[maxn];    //为了简洁,当然也可以直接展开写.
void init(){ for(int i=0;i<=n;i++) pre[i]=i; }   
int Find(int x){ return pre[x]==x?x:pre[x]=Find(pre[x]); }
bool cmp(node a,node b){ return a.w<b.w; }
int kruskal(int flag)     //flag来标记是第一次进来还是标记过的边进来.
{
    int num=0;
    int sum=0;
    for(int i=0;i<m;i++){
        if(i==flag) continue;    //遇到标记过的边就删除.
        int u=Find(s[i].u);
        int v=Find(s[i].v);
        if( u != v){
            pre[v]=u;
            sum+=s[i].w;
            num++;
            if(flag==-1)
                used.push_back(i);    //用过的边全部保存在used容器中.
        }
        if(num==n-1)
            break;
    }
    int cnt=0;
    for(int i=1;i<=n;i++){    //判断是否是最小生成树.
        if(pre[i]==i)
            cnt++;
    }
    if(cnt>1)
        return inf;
    return sum;
}

int main()
{
    int t;
    cin >> t;
    while(t--){
        scanf("%d %d",&n,&m);
        if(n==1 && m==0){         //特判这一种情况.
            printf("Case #%d : No second way\n",cas++);
            continue;
        }
        init();
        used.clear();
        for(int i=0;i<m;i++){
            scanf("%d %d %d",&s[i].u,&s[i].v,&s[i].w);
        }
        sort(s,s+m,cmp);
        int ans=inf;
        ans=kruskal(-1);
        printf("Case #%d : ",cas++);
        if(ans==inf){
            printf("No way\n");
            continue;
        }
        ans=inf;
        for(int i=0;i<used.size();i++){
            init();
            int use=used[i];
            ans=min(ans,kruskal(use));      //循环选出次小生成树!
        }
        if(ans==inf){
            printf("No second way\n");
            continue;
        }
        printf("%d\n",ans);
    }
}