[hdoj1863]畅通工程

思路：

因为之前做了一道题叫还是畅通工程（hdoj1233），题意几乎一样，我用的普利姆算法，

只在原程序的继续上加了判断语句，

if(min==1000000){
cout<<'?'<<endl;
return;

似乎还做了点细微调整，就ac了，哈哈。

[cpp]
//hdoj1863
#include<iostream>
using namespace std;
int path[101][101];
int flag[101];
int closepath[101];
int sum;

void prim(int x,int n)
{
    int i,count=n-1,pose=x;
    flag[x]=1;
    for(i=1;i<=n;i++)
        closepath[i]=path[x][i];
    while(count)
    {
        int min=1000000;
        for(i=1;i<=n;i++)
            if(min>closepath[i] && !flag[i])
            {
                min=closepath[i];
                pose=i;
            }
        if(min==1000000){
            cout<<'?'<<endl;
            return;
            }
        count--;sum+=min;
        flag[pose]=1;
        for(i=1;i<=n;i++)
            if(closepath[i]>path[pose][i] && !flag[i])
                closepath[i]=path[pose][i];
    }
        cout<<sum<<endl;
}

void main()
{
   int n,m,i,j,begin,end,len;
   while(cin>>n,n)//道路数
   {
       cin>>m;//村庄数
          memset(flag,0,sizeof(flag));
          sum=0;
          for(i=1;i<=m;i++)
              for(j=1;j<=m;j++)
              {
                 if(i==j)
                     path[i][j]=0;
                 else
                     path[i][j]=1000000;
              }
          for(i=1;i<=n;i++)
          {
             cin>>begin>>end>>len;
             if(len<path[begin][end])//
             path[begin][end]=path[end][begin]=len;
          }
          prim(1,m);

   }
}

补充：软件开发 , C++ ,