Civil and Evil Engineer（普林姆）

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=198#problem/E

水题一道，题意就是让求一遍最小生成树与最大生成树，但我因为Each case contains a blank line and an integer n (1 ≤ n ≤ 100) denoting the number of houses.这句话错了三遍，有两种解决方案，一不用管空格，二gets(str);

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

#define N 1000001

int map[][],map1[][];

int v[],v1[];

int dis[],dis1[];

int n;

int Primmin()

{

    int min,k,sum=;

    memset(v,,sizeof(v));

    v[]=;

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

      dis[i]=map[][i];

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

    {

        min=N;

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

        {

            if(v[j]==&&min>dis[j])

            {

                min=dis[j];

                k=j;

            }

        }

        v[k]=;

        sum=sum+min;

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

        {

            if(v[j]==&&dis[j]>map[k][j])

            {

                dis[j]=map[k][j];

            }

        }

    }

    return sum;

}

int Primmax()

{

    int min,k,sum=;

    memset(v1,,sizeof(v1));

    v1[]=;

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

      dis1[i]=map1[][i];

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

    {

        min=;

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

        {

            if(v1[j]==&&min<dis1[j])

            {

                min=dis1[j];

                k=j;

            }

        }

        sum=sum+min;

        v1[k]=;

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

        {

            if(v1[j]==&&dis1[j]<map1[k][j])

            {

                dis1[j]=map1[k][j];

            }

        }

    }

    return sum;

}

int main()

{

    int T,K=;

    char ch[];

    scanf("%d",&T);

    while(T--)

    {

        K++;

        gets(ch);

        scanf("%d",&n);

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

        {

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

            {

                map[i][j]=N;

                map[j][i]=N;

            }

            map[i][i]=;

        }

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

        {

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

            {

                map1[i][j]=;

                map1[j][i]=;

            }

        }

        int xx,yy,zz;

        while(scanf("%d%d%d",&xx,&yy,&zz)!=EOF)

        {

            if(xx==&&yy==&&zz==)  break;

            if(map[xx][yy]>zz)

            {

                map[xx][yy]=zz;

                map[yy][xx]=zz;

            }

            if(map1[xx][yy]<zz)

            {

                map1[xx][yy]=zz;

                map1[yy][xx]=zz;

            }

        }

        int sum1=Primmin();

        int sum2=Primmax();

         long long int tt=sum1+sum2;

        if(tt%==)

        {

             tt=tt/;

             printf("Case %d: %lld\n",K,tt);

        }

        else printf("Case %d: %lld/2\n",K,tt);

    }

    return ;

}

巴特西

Civil and Evil Engineer（普林姆）

最新文章

热门文章