Asia Regional Contest, Tokyo, 2014 There is No Alternative（prim及kluskal）

题目链接：点击打开链接

文章转载自：xuanqis.com

Description

ICPC (Isles of Coral Park City) consist of several beautiful islands.

The citizens requested construction of bridges between islands to resolve inconveniences of using boats between islands, and they demand that all the islands should be reachable from any other islands via one or more bridges.

The city mayor selected a number of pairs of islands, and ordered a building company to estimate the costs to build bridges between the pairs. With this estimate, the mayor has to decide the set of bridges to build, minimizing the total construction cost.

However, it is difficult for him to select the most cost-efficient set of bridges among those connecting all the islands. For example, three sets of bridges connect all the islands for the Sample Input 1. The bridges in each set are expressed by bold edges in Figure F.1.

Figure F.1. Three sets of bridges connecting all the islands for Sample Input 1
Figure F.1. Three sets of bridges connecting all the islands for Sample Input 1

As the first step, he decided to build only those bridges which are contained in all the sets of bridges to connect all the islands and minimize the cost. We refer to such bridges as no alternative bridges. In Figure F.2, no alternative bridges are drawn as thick edges for the Sample Input 1, 2 and 3.

Write a program that advises the mayor which bridges are no alternative bridges for the given input.

Input

The input consists of several tests case.

Figure F.2. No alternative bridges for Sample Input 1, 2 and 3
Figure F.2. No alternative bridges for Sample Input 1, 2 and 3

N MS1 D1 C1⋮SM DM CM

For each test, the first line contains two positive integers N and M . N represents the number of islands and each island is identified by an integer 1 through N. M represents the number of the pairs of islands between which a bridge may be built.

Each line of the next M lines contains three integers Si, Di and Ci (1 ≤ i ≤ M) which represent that it will cost Ci to build the bridge between islands Si and Di. You may assume 3 ≤ N ≤ 500, N − 1 ≤ M ≤ min(50000, N(N − 1)/2), 1 ≤ Si < Di ≤ N, and 1 ≤ Ci ≤ 10000. No two bridges connect the same pair of two islands, that is, if i ≠ j and Si = Sj , then Di ≠ Dj. If all the candidate bridges are built, all the islands are reachable from any other islands via one or more bridges.

Output

Output two integers, which mean the number of no alternative bridges and the sum of their construction cost, separated by a space.

Sample Input

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

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

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

3 3
1 2 1
2 3 1
1 3 1

Sample Output

1 3
3 9
2 4
0 0
Hint

Source

Asia Regional Contest, Tokyo, 2014

题意

给出一个图，求最小生成树不可替代的边的个数和权值和，就是去掉该边最小生成树值更大或者没有的边的个数和权值和。

思路

先求出最初没去掉边的最小生成树，并记录最小生成树的边，其他不是最小生成树边的不用考虑。接着一条条的尝试去掉其中的边，计算最小生成树，如果更原先的最小生成树值相同，则是可替代边，值不同则是不可替代边。

代码

prim

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;  
const int INF =0x3f3f3f3f;   
const int MAXN = 510;  //点的最大值 
bool vis[MAXN];  //是否在集合中 
int lowc[MAXN];  //集合中元素到该元素的最小值 
int cost[MAXN][MAXN];  //每两个点联通的花费 
int label[MAXN];  //标记该节点与哪个节点组成最小生成树的边 
bool flag=false;  //设置只有最初求最小生成树才记录label 
int Prim( int n){  //使用prim算法 
    int ans=0;  
    memset(vis, false, sizeof(vis));  
    vis[0]=true;  
    for(int i=1;i<n;i++) lowc[i]=cost[0][i];  
    for(int i=1; i<n; i++){
        int minc = INF;  
        int p=-1;  
        for(int j=0;j<n;j++){
            if(!vis[j] && minc > lowc[j]){
                minc=lowc[j];
                p=j;    
            }
        }
        if(minc==INF) return -1;  
        ans += minc;  
        vis[p]=true;  
        if(!label[p])label[p]=0;
        for(int j=0;j<n;j++){
            if(!vis[j] && lowc[j] > cost[p][j]){
                lowc[j] = cost[p][j];  
                if(!flag)label[j]=p;  //如果是最初一次，就记录label 
            }
        }
    }
    return ans;  
}
void init(){  //初始化 
    memset(cost,0x7f,sizeof(cost));  //设置一个大的值 
    memset(label,0,sizeof(label));
    flag=false;  
}
int main(){
    //freopen("2.txt", "r", stdin);  
    int n,m;  
    while(~scanf("%d%d", &n, &m)){
        init();  
        for(int i=1;i<=m;i++){  //输入数据 
            int u, v, w;  
            scanf("%d%d%d", &u, &v, &w);  
            cost[u-1][v-1]=cost[v-1][u-1]=w;  
        }
        int best=Prim(n);   //这个是没去掉边的最小生成树 
        flag=true;  //之后的不再计算label 
        int sum=0; //记录各不可替代边的总和 
        int sumnum=0;  //记录不可替代边的个数 
        for(int i=1;i<n;i++){ //逐条去掉最小生成树的边，看是否是原来的最小生成树 
            int w=cost[label[i]][i];
            cost[label[i]][i]=cost[i][label[i]]=INF;  
            int temp=Prim(n);  
            if(temp == -1 || temp != best){  //去掉该边就不是原来的最小生成树，不可替代 
                sumnum++;  
                sum += w;  
            }
            cost[label[i]][i]=cost[i][label[i]]=w;  //恢复 
        }
        printf("%d %d\n", sumnum,sum);  
    }
}

kluskal

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;  
const int MAXN = 510;  //点数 
const int MAXM=51000;  //最大边数 
const int INF = 0x3f3f3f3f;  
int F[MAXN];  //并查集用到 
struct Edge{  
    int u,v,w;  
    bool flag;  //是否是最小生成树的边 
}edge[MAXM];  
int tol;  
void addedge(int u, int v, int w){  //添加边 
    edge[tol].flag=false;  
    edge[tol].u=u;  
    edge[tol].v=v;  
    edge[tol++].w=w;  
}
bool cmp(Edge a, Edge b){  //比较函数 
    return a.w < b.w;  
}
int find(int x){  //找到最终的祖先 
    int temp=x;  
    while(F[x] != -1){
        x=F[x];
    } 
    while(F[temp] != -1){
        int num=F[temp];  
        F[temp]=x;  
        temp=num;  
    }
    return x;  
}
bool flag=false;  //设置只有第一次才会记录最小生成树的边 
int Kluskal(int n,int num){  //kluskal算法求最小生成树 
    memset(F,-1,sizeof(F));  
    int cnt=0;
    int ans=0;  
    for(int i=0;i<tol;i++){
        if(i==num)continue;  
        int u=edge[i].u;  
        int v=edge[i].v;  
        int w=edge[i].w;  
        int t1=find(u);  
        int t2=find(v);  
        if(t1 != t2){
            if(!flag)edge[i].flag=true;  //只有第一次才记录边 
            ans += w;  
            F[t1]=t2;  
            cnt++;  
        }
        if(cnt == n-1)break;  
    }
    if(cnt < n-1) return -1;  
    return ans;  
}

void init(){  //初始化 
    tol=0;  
    memset(edge,0,sizeof(edge));  
    flag=false;  
}

inline int Found(int start){
    for(int i=start;i<tol;i++){
        if(edge[i].flag){
            edge[i].flag=false;  
            return i;  
        }
    }
    return -1;  
}
int main(){
    //freopen("2.txt", "r", stdin);  
    int n,m;  
    while(~scanf("%d%d", &n, &m)){
        init();  
        for(int i=1; i<=m; i++){  //输入数据 
            int numa, numb,numc;  
            scanf("%d%d%d", &numa, &numb, &numc);  
            addedge(numa,numb, numc);  
        }
        sort(edge,edge+tol,cmp);  
        int ans = Kluskal(n,-1); //最初的最小生成树 
        flag=true;  
        int sumnum=0;  //不可替代边的权值和 
        int sum=0;     //不可替代边的个数 
        int num=0;  
        for(int i=1;i<=n-1;i++){  //一个个的去掉n-1个 
            num = Found(num);
            int temp=Kluskal(n,num);  
            if(temp != ans){  //去掉不是原来的值，说明不可替代 
                sum+= edge[num].w;  
                sumnum++;  
            }
        }
        printf("%d %d\n",sumnum, sum);  
    }
}