UVA10600 ACM Contest and Blackout

用prim算法求最小生成树和次小生成树~

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=;

const int inf=1e9;

int g[maxn][maxn],d[maxn],visit[maxn],pre[maxn],c[maxn][maxn],N,M;

int path[maxn][maxn];//记录最小生成树里两点之间的路径

void init () {

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

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

    g[i][j]=inf,c[i][j]=,path[i][j]=;

}

int prim (int s) {

    fill (d,d+maxn,inf);

    fill (visit,visit+maxn,);

    for (int i=;i<=N;i++) pre[i]=i;

    d[s]=;

    int ans=;

    for (int i=;i<=N;i++) {

        int u=-,min=inf;

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

        if (visit[j]==false&&d[j]<min) {

            u=j;

            min=d[j];

        }

        if (u==-) return -;

        visit[u]=;

        ans+=d[u];

        if (pre[u]!=u) c[u][pre[u]]=c[pre[u]][u]=;

        for (int v=;v<=N;v++) {

            if (!visit[v]&&g[u][v]!=inf&&g[u][v]<d[v]) d[v]=g[u][v],pre[v]=u;

            if (visit[v]&&v!=u) path[u][v]=path[v][u]=max(path[pre[u]][v],d[u]);

        }

    }

    return ans;

}

int main () {

    int T;

    scanf ("%d",&T);

    while (T--) {

        scanf ("%d %d",&N,&M);

        int x,y;

        init ();

        for (int i=;i<M;i++) {

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

            scanf ("%d",&g[x][y]);

            g[y][x]=g[x][y];

        }

        int mst=prim ();

        int ans=inf;

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

        for (int j=;j<=N;j++) {

            if (i!=j&&!c[i][j]) {

                ans=min(ans,mst-path[i][j]+g[i][j]);

            }

        }

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

    }

    return ;

}