[prim]aizuoj：There is No Alternative

题目地址：http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2014/F.pdf

大致题意：

       求出一个带权无向图中哪些边一定是最小生成树的一部分，输出这边的数量和他们权值的和。

 

大致思路：

      先求一遍prim，记录哪些边在这个最小生成树上。然后依次枚举删去这些边，如果删掉第i条边之后最小生成树长度增加，则第i条边一定在最小生成树上。

 

附上这辈子写过的最丑的代码

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000;
const int mMax=100010;
const int inf=1000010;

int n,m,map[nMax][nMax],mark[mMax],mpp[nMax][nMax];

int dis[nMax],fff[nMax],ans,mintree[nMax][2],nk;
int prim(bool isis){   //  自己的prim模板。
    int i, j, now,aaa,bbb;
    int  min_node, min_edge;
    for(i = 1; i <=n; i ++)
        dis[i] = inf-10;
    now = 1;
    ans = 0;
    nk=1;
    for(i = 0; i < n-1; i ++){
        dis[now] = -1;    //   将dis[]的值赋-1，表示已经加入生成树中。
        min_edge = inf;
        for(j = 1; j <= n; j ++)    //   更新每个顶点所对应的dis[]值。
            if(now != j && dis[j] >= 0 ){
                if(map[now][j]<dis[j]){
                    dis[j]=map[now][j];
                    fff[j]=now;
                }
                if(dis[j] < min_edge){
                    min_edge = dis[j];
                    min_node = j;
                }
            }
        now = min_node;
       if(isis==1){
            aaa=now;
            bbb=fff[now];
            mintree[nk][0]=aaa;
            mintree[nk++][1]=bbb;
       }
        ans += min_edge;
    }
    return ans;
}

int val[mMax];
int main(){
    int i,j,a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(i=1;i<=n;i++)for(j=1;j<=n;j++)map[i][j]=inf;
        memset(mark,0,sizeof(mark));
        for(i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]=map[b][a]=c;
            mpp[a][b]=mpp[b][a]=i;
            val[i]=c;
        }

        int sum = prim(1);
        a=map[mintree[1][0]][mintree[1][1]];
        map[mintree[1][0]][mintree[1][1]]=map[mintree[1][1]][mintree[1][0]]=inf;
        if(sum!=prim(0)){
            mark[mpp[mintree[1][0]][mintree[1][1]]]=1;
        }
        for(i=2;i<=n-1;i++){
            map[mintree[i-1][0]][mintree[i-1][1]]=map[mintree[i-1][1]][mintree[i-1][0]]=a;
            if(mark[mpp[mintree[i][0]][mintree[i][1]]])continue;
            a=map[mintree[i][0]][mintree[i][1]];
            map[mintree[i][0]][mintree[i][1]]=map[mintree[i][1]][mintree[i][0]]=inf;
            b=prim(0);
//            cout<<b<<endl;
            if(sum!=b){
                mark[mpp[mintree[i][0]][mintree[i][1]]]=1;
            }
        }
        ans=0,sum=0;
        for(i=1;i<=m;i++){
            if(mark[i]){
                ans++;
                sum+=val[i];
            }
        }
        printf("%d %d\n",ans,sum);
    }
    return 0;
}