[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); 
 
   } 
}