HDU-1232--畅通工程(最小生成树)

Problem Description

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

Input

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最少还需要建设的道路数目。

Sample Input

Sample Output

Hint

Hint Huge input, scanf is recommended.

Source

浙大计算机研究生复试上机考试-2005年

Recommend

JGShining

又是一道最小生成树的裸题

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<map>

#include<iomanip>

#define INF 0x7ffffff

#define MAXN 1100

using namespace std;

const double eps=1e-;

const double PI=acos(-);

const int MAXN2=;//

int G[MAXN][MAXN];

int s[MAXN];

int n,m;

struct edge

{

    int x;

    int y;

}e[MAXN2];

int f(int x)

{

    if(x==s[x])

        return x;

    s[x]=f(s[x]);

    return s[x];

}

int merg(int a,int b)

{

    int x=f(a),y=f(b);

    if(x!=y){

        s[x]=y;

        return ;

    }

    return ;

}

void init()

{

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

        s[i]=i;

    }

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("data.in", "r", stdin);

    #endif

    std::ios::sync_with_stdio(false);

    std::cin.tie();

    //并查集

    int a,b;

    int res;

    while(cin>>n){

        init();

        if(n==)

            continue;

        cin>>m;

        struct edge tmp;

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

            cin>>a>>b;

            merg(a,b);

        }

        res=;

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

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

                if(!merg(i,j)){

                    res++;

                }

            }

        }

        cout<<res<<endl;

    }

}

巴特西

HDU-1232--畅通工程(最小生成树)

最新文章

热门文章