HDUOJ-1863スムーズエンジニアリング

開通工事
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 13865    Accepted Submission(s): 5732
Problem Description
省政府の「円滑な工事」の目標は、全省のどの2つの村の間でも道路交通を実現させることである(しかし、直接的な道路がつながっているとは限らず、間接的に道路を通過すればよい).調査評価を経て、得られた統計表には、道路を建設する可能性のあるいくつかの道路のコストがリストされている.プログラムを作成して、全省の円滑化に必要な最低コストを計算してください.
 
 
Input
テスト入力には、いくつかのテスト例が含まれます.各試験例の1行目は、評価された道路数N、村数M(<100)を与える.その後のN 
行は村間道路のコストに対応し、各行には2つの村の番号と、この2つの村間道路のコスト(正の整数)のペアの正の整数が与えられます.簡単にするために、村は1からM番までです.Nが0の場合、すべての入力が終了し、対応する結果は出力されません.
 
 
Output
各テスト例に対して、1行に全省の円滑化に必要な最低コストを出力する.統計データがスムーズでない場合は「?」を出力します.
 
 
Sample Input
3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
 
 
Sample Output
3 ?
 
 
Source
浙大コンピュータ大学院生の再試験の上機試験-2007年
 
 
Recommend
 
 
最小生成ツリー...
プリム...
简単.问题解决の考え方.キーコードの详细
コード:

#include<stdio.h>

#include<string.h>

const int inf=0x3f3f3f3f;

int vis[101],lowc[101];

int sta[101][101];

int prim(int cost[][101], int n)

{

    int i,j,p;

    int minc,res=0;

    memset(vis , 0 , sizeof(vis));

    vis[0] = 1;

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

        {

            lowc[i] = cost[0][i];

        }

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

    {

        minc=inf ; //<         >

        p=-1;

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

        {

            if(0==vis[j] && minc > lowc[j] )

            {

                minc = lowc[j];

                p = j;

            }

        }

        if(inf == minc) return -1;  //     

        res += minc ;

        vis[p] = 1;

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

        {

            if(0==vis[j] && lowc[j] > cost[p][j])

                lowc[j] = cost[p][j];

        }

    }

    return res ;

}

int main( void )

{

    int n,m,i,j,a,b,c;

    while(scanf("%d%d",&n,&m)!=EOF&&n)

    {

        for(i=0;i<m ; i++)

        {

            for(j=0 ; j<m ; j++ )

            {

                sta[i][j]=inf;  //<             00>

            }

        }

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

        {

            scanf("%d%d%d",&a,&b,&c);

            sta[a-1][b-1]=sta[b-1][a-1]=c;

        }

        int ans=prim(sta,m);

        if(ans==-1)

            printf("?
");

        else

            printf("%d
",ans);

    }

    return 0;

}