poj1679 次小生成树

prim方法:先求过一遍prim，同时标记使用过得边。然后同时记录任意2点间的最大值。

每次加入一条新的边，会产生环，删去环中的最大值即可。

#include<stdio.h>

#include<string.h>

#define INF 99999999

const int maxn = ;

int map[maxn][maxn],vis[maxn],dis[maxn],n,pre[maxn],m,used[maxn][maxn];

int maxd[maxn][maxn];

int max(int x,int y){return x>y?x:y;}

int min(int x,int y){return x<y?x:y;}

void init()

{

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=n;j++)

        {

            if(i==j)map[i][j]=;

            else map[i][j]=INF;

        }

    }

}

int prim()

{

    int ans=;

    int i,j,pos;

    memset(maxd,,sizeof(maxd));

    for(i=;i<=n;i++)

    {

        dis[i]=map[][i];

        vis[i]=;

        pre[i]=;

    }

    vis[]=;

    pre[]=-;

    for(i=;i<n;i++)

    {

        int minc=INF;

        for(j=;j<=n;j++)

        {

            if(!vis[j]&&minc>dis[j])

            {

                pos=j;

                minc=dis[j];

            }

        }

        vis[pos]=;

        ans+=minc;

        used[pre[pos]][pos]=used[pos][pre[pos]]=;

        for(j=;j<=n;j++)

        {

            if(vis[j])

                maxd[pos][j]=maxd[j][pos]=max(maxd[j][pre[pos]],dis[pos]);

        }

        for(j=;j<=n;j++)

        {

            if(!vis[j]&&dis[j]>map[pos][j])

            {

                dis[j]=map[pos][j];

                pre[j]=pos;

            }

        }

    }

    return ans;

}

int dfs(int x)

{

    int ans=INF;

    int i,j;

    for(i=;i<=n;i++)

    {

        for(j=;j<=n;j++)

        {

            if(i==j)continue;

            if(map[i][j]!=INF&&!used[i][j])

            {

                ans=min(ans,x+map[i][j]-maxd[i][j]);

            }

        }

    }

    return ans;

}

int main()

{

    int i,j,t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        init();

        for(i=;i<m;i++)

        {

            int x,y,z;

            scanf("%d%d%d",&x,&y,&z);

            if(map[x][y]>z)

            map[x][y]=map[y][x]=z;

        }

        memset(used,,sizeof(used));

        int mst=prim();

        int second_mst=dfs(mst);

        if(second_mst!=mst)

            printf("%d\n",mst);

        else printf("Not Unique!\n");

    }

}