程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1879 繼續暢通工程

HDU 1879 繼續暢通工程

編輯：C++入門知識

HDU 1879 繼續暢通工程

繼續暢通工程

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 15492 Accepted Submission(s): 6694

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

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

當N為0時輸入結束。
Output 每個測試用例的輸出占一行，輸出全省暢通需要的最低成本。
Sample Input

Sample Output

3
1
0

Author ZJU
Source 浙大計算機研究生復試上機考試-2008年
一個prim水題。。超時了4次，原因是用cin輸入，改成scanf輸入瞬間AC，，關鍵點:修過的路距離設為0就好了。

#include 
#include 
#include 
#include
#include 
#include 
#include 
#include
#include 
#include 
#include 
using namespace std;
#define inf 0x6f6f6f6f
#define mod 10
int dis[105];
int vis[105];
int mat[105][105];
int n,ans;
void prim()
{
    memset(vis,0,sizeof(vis));
    int i,j,k,min1;
    for(i=1; i<=n; i++)
        dis[i]=mat[1][i];
    vis[1]=1;
    for(i=1; imat[k][j])
                dis[j]=mat[k][j];
        }
    }
}
int main()
{
    int i;
    while(scanf("%d",&n)&&n)
    {
        int s,e,l,flag;
        memset(mat,0,sizeof(mat));
        for(i=1; i<=n*(n-1)/2; i++)
        {
            scanf("%d%d%d%d",&s,&e,&l,&flag);
            if(flag)   //修過的話
                mat[s][e]=mat[e][s]=0;//距離設為0.
            else
                mat[s][e]=mat[e][s]=l;
        }
        ans=0;
        prim();
        printf("%d\n",ans);
    }
    return 0;
}