Problem: Example

Input

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


Output

1 3

Solution (in CPP):

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

class edge{
public:
    long long u,v,nex,w,loc;
};edge e[mMax];
long long k,head[nMax];//head[i]是以点i&#20026;起点的&#38142;表&#22836;部

void addedge(long long a,long long b,long long c,long long loc){
  //  cout<<a<<" add "<<b<<" with "<<c<<endl;
    e[k].u=a;
    e[k].v=b;
    e[k].w=c;
    e[k].loc=loc;
    e[k].nex=head[a];
    head[a]=k;k++;
}
long long n,m,map[nMax][nMax],mark[mMax],mpp[nMax][nMax];

long long dep,nbridge;
long long dfn[nMax],low[nMax],res[mMax];

void Tarjan(long long u,long long fa){                        //我的割&#36793;模版
    dfn[u]=low[u]=++dep;
    long long flag = 1 ;
    for(long long i=head[u];i;i=e[i].nex){
        long long v=e[i].v;
        if ( v == fa && flag ) {
            flag = 0 ;
            continue ;
        }
        if(!dfn[v]){
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
               res[++nbridge]=e[i].loc;
            }
        }
        else{
            low[u]=min(low[u],dfn[v]);
        }
    }
}


long long dis[nMax],fff[nMax],ans,mintree[nMax][2],nk;
long long prim(bool isis){   //  自己的prim模板。
    long long i, j, now,aaa,bbb;
    long long  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[]的&#20540;&#36171;-1，表示已&#32463;加入生成&#26641;中。
        min_edge = inf;
        for(j = 1; j <= n; j ++)    //   更新&#27599;个&#39030;点所&#23545;&#24212;的dis[]&#20540;。
            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;
}

long long val[mMax];
int main(){
    long long i,j,a,b,c;
    while(scanf("%lld%lld",&n,&m)!=EOF){
        k=1;
        memset(head,0,sizeof(head));
        //memset(map,-1,sizeof(map));
        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("%lld%lld%lld",&a,&b,&c);
            map[a][b]=map[b][a]=c;
            addedge(a,b,c,i);
            addedge(b,a,c,i);
            mpp[a][b]=mpp[b][a]=i;
            val[i]=c;
        }

        dep=0;
        nbridge=0;
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        for(i=1;i<=n;i++)if(!dfn[i])Tarjan(i,-1);
//        for(i=1;i<=nbridge;i++){
//            mark[res[i]]=1;
//        }
        long long sum = prim(1);
//        cout<<"ddd "<<sum<<endl;
        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("%lld %lld\n",ans,sum);
    }
    return 0;
}