hdu1879 繼續暢通工程 (最小生成樹之prim 算法)

Problem Description
省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可）。現得到城鎮道路統計表，表中列出了任意兩城鎮間修建道路的費用，以及該道路是否已經修通的狀態。現請你編寫程序，計算出全省暢通需要的最低成本。

Input
測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數目N ( 1< N < 100 )；隨後的 N(N-1)/2 行對應村莊間道路的成本及修建狀態，每行給4個正整數，分別是兩個村莊的編號（從1編號到N），此兩村莊間道路的成本，以及修建狀態：1表示已建，0表示未建。

當N為0時輸入結束。

Output
每個測試用例的輸出占一行，輸出全省暢通需要的最低成本。

Sample Input
3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0

Sample Output
3
1
0

#include<stdio.h>   int node[105],n,sum,map[105][105],s[105],INF=10000000;  void set_first()  {      for(int i=1;i<=n;i++)      {          node[i]=INF; s[i]=0;          for(int j=1;j<=n;j++)          map[i][j]=INF;      }  }  void Prim(int m)  {      int min;      s[m]=1; sum=0;      for(int k=2;k<=n;k++)      {          for(int i=1;i<=n;i++)          if(s[i]==0&&node[i]>map[m][i])          node[i]=map[m][i];            min=INF;          for(int j=1;j<=n;j++)          if(s[j]==0&&min>node[j])          {              min=node[j]; m=j;          }          s[m]=1; sum+=min;      }  }  int main()  {      int a,b,p,tru;      while(scanf("%d",&n)>0&&n)      {          set_first();          for(int i=1;i<=n*(n-1)/2;i++)          {              scanf("%d%d%d%d",&a,&b,&p,&tru);              if(map[a][b]>p)   //判斷重邊               map[a][b]=map[b][a]=p;              if(tru>0)   //把建好的道路長度（權值）變成0               map[a][b]=map[b][a]=0;          }          Prim(1);  //以1為起點           printf("%d\n",sum);      }  }  #include<stdio.h>
int node[105],n,sum,map[105][105],s[105],INF=10000000;
void set_first()
{
    for(int i=1;i<=n;i++)
    {
        node[i]=INF; s[i]=0;
        for(int j=1;j<=n;j++)
        map[i][j]=INF;
    }
}
void Prim(int m)
{
    int min;
    s[m]=1; sum=0;
    for(int k=2;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        if(s[i]==0&&node[i]>map[m][i])
        node[i]=map[m][i];

        min=INF;
        for(int j=1;j<=n;j++)
        if(s[j]==0&&min>node[j])
        {
            min=node[j]; m=j;
        }
        s[m]=1; sum+=min;
    }
}
int main()
{
    int a,b,p,tru;
    while(scanf("%d",&n)>0&&n)
    {
        set_first();
        for(int i=1;i<=n*(n-1)/2;i++)
        {
            scanf("%d%d%d%d",&a,&b,&p,&tru);
            if(map[a][b]>p)   //判斷重邊
            map[a][b]=map[b][a]=p;
            if(tru>0)   //把建好的道路長度（權值）變成0
            map[a][b]=map[b][a]=0;
        }
        Prim(1);  //以1為起點
        printf("%d\n",sum);
    }
}