继续畅通project

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 14309 Accepted Submission(s): 6228

Problem Description

省政府“畅通project”的目标是使全省不论什么两个村庄间都能够实现公路交通（但不一定有直接的公路相连，仅仅要能间接通过公路可达就可以）。现得到城镇道路统计表，表中列出了随意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编敲代码，计算出全省畅通须要的最低成本。

Input

測试输入包括若干測试用例。每一个測试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行相应村庄间道路的成本及修建状态，每行给4个正整数，各自是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

当N为0时输入结束。

Output

每一个測试用例的输出占一行，输出全省畅通须要的最低成本。

Sample Input

Sample Output

3

1

0



#include <stdio.h>

#include<string.h>

#include <algorithm>

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;

}
#include <stdio.h>

#include<string.h>

#include <algorithm>

int city[5000];

using namespace std;

struct Road

{

    int c1;

	int c2;

	int cost;

	int state;

};

Road road[110];

bool cmp(Road a,Road b)

{

	if(a.cost<b.cost)

	return 1;

return 0;

}

int find(int a)

{

    if(city[a]==-1)

        return a;

return city[a]=find(city[a]);

}

bool merge(int x, int y)

{

	int fx,fy;

     fx = find(x);

     fy = find(y);

    if(fx == fy)   return 0;

    else if(fx < fy)                //不能省去

           city[fy] = fx;

    else

           city[fx] = fy;

return 1;

}

int main()

{

    int n, m;

    while(scanf("%d",&n),n)

    {

    	m=n*(n-1)/2;

    	int i;

    	int count = 0;

    	int sum = 0;

        memset(city,-1,sizeof(city));

        for(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,cmp);

        for(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;

}

村庄

HDoj-1879-畅通project-并查集

继续畅通project