Blog·Tanky WooABOUTRSS

HDOJ 1233 还是畅通工程| HDOJ 1863 畅通工程 | HDOJ 1879 继续畅通工程

16 Sep 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
资料
最小生成树(MST)讲解请看: [http://www.wutianqi.com/?p=1284](http://www.wutianqi.com/?p=1284)

HDOJ 1233 还是畅通工程: 题目传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1233

解答报告:

#include 
#include 
using namespace std;

typedef struct Road
{
    int c1, c2, cost;
}Road;

bool myCompare(const Road &a;, const Road &b;)
{
    if(a.cost < b.cost)
        return 1;
    return 0;
}

Road road[5051];
int city[101];

int Find(int n)
{
    if(city[n] == -1)
        return n;
    return city[n] = Find(city[n]);
}

bool Merge(int s1, int s2)
{
    int r1 = Find(s1);
    int r2 = Find(s2);
    if(r1 == r2)
        return 0;
    if(r1 < r2)
        city[r2] = r1;
    else
        city[r1] = r2;
    return 1;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int n;
    while(scanf("%d", &n;) && n)
    {
        int m = n*(n-1)/2;
        memset(city, -1, sizeof(city));
        for(int i=0; i
**HDOJ 1863 畅通工程**
题目传送门:
[http://acm.hdu.edu.cn/showproblem.php?pid=1863](http://acm.hdu.edu.cn/showproblem.php?pid=1863)

好吧,这题是送你的,因为这题和1233基本上没区别。。。。
解答报告:

```cpp

#include 
#include 
using namespace std;

typedef struct Road
{
    int c1, c2, cost;
}Road;

bool myCompare(const Road &a;, const Road &b;)
{
    if(a.cost < b.cost)
        return 1;
    return 0;
}

Road road[5051];
int city[101];

int Find(int n)
{
    if(city[n] == -1)
        return n;
    return city[n] = Find(city[n]);
}

bool Merge(int s1, int s2)
{
    int r1 = Find(s1);
    int r2 = Find(s2);
    if(r1 == r2)
        return 0;
    if(r1 < r2)
        city[r2] = r1;
    else
        city[r1] = r2;
    return 1;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m;// m-道路条数, n-村庄数
    while(scanf("%d %d", &m;, &n;) && m)
    {
        memset(city, -1, sizeof(city));
        for(int i=0; i
**HDOJ 1879 继续畅通工程** 
题目传送门:
[http://acm.hdu.edu.cn/showproblem.php?pid=1879](http://acm.hdu.edu.cn/showproblem.php?pid=1879)
这题币上面两题要活一些。
可以考察大家对MST的掌握。
好好分析代码,相信你能看懂的。

```cpp

#include 
#include 
using namespace std;
typedef struct Road
{
    int c1, c2, cost, state;
}Road;

bool myCompare(const Road &a;, const Road &b;)
{
    if(a.cost < b.cost)
        return 1;
    return 0;
}

Road road[5051];
int city[101];

int Find(int n)
{
    if(city[n] == -1)
        return n;
    return city[n] = Find(city[n]);
}

bool Merge(int s1, int s2)
{
    int r1 = Find(s1);
    int r2 = Find(s2);
    if(r1 == r2)
        return 0;
    if(r1 < r2)
        city[r2] = r1;
    else
        city[r1] = r2;
    return 1;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int n;
    while(scanf("%d", &n;) && n)
    {
        int m = n*(n-1)/2;
        memset(city, -1, sizeof(city));
        int count = 0;
        for(int i=0; i<m; ++i)
        {
            scanf("%d %d %d %d", &road[i].c1, &road[i].c2, &road[i].cost, &road[i].state);
            if(road[i].state == 1)
            {
                count ++;
                Merge(road[i].c1, road[i].c2);
            }
        }
        sort(road, road+m, myCompare);
        int sum = 0;
        for(int i=0; i<m; ++i)
        {
            if(Merge(road[i].c1, road[i].c2) && road[i].state == 0)
            {
                count ++;
                sum += road[i].cost;
            }
            if(count == n-1)
                break;
        }
        printf("%d\n", sum);
    }
    return 0;
}