HDU1879繼續暢通工程

NO IMAGE

繼續暢通工程

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

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
暢通工程總的來說就是最短路 最小生成樹 把兩種最小生成樹(普利姆,克魯斯卡爾)四種最短路(Bellman-ford演算法 & Dijkstra演算法 & floyd演算法 & SPFA演算法 )
#最小生成樹
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define N 5100
struct node
{
int u,v,w;
int flag;
} q[N];
int cmp(node x,node y)
{
return x.w<y.w;
}
int p[110];
int m,i;
void init ()
{
for(i=0; i<=m; i  )
{
p[i] = i;
}
memset(q,0,sizeof(q));
}
int find(int x)//並查集的find
{
return p[x] == x ? x : find(p[x]);
}
void bin(int x,int y)
{
int a = find(x);
int b = find(y);
p[b] = a;
}
int main()
{
while(scanf("%d",&m),m)
{
init();
int ans = 0;
int A = m*(m-1)/2;
for (i = 0; i < A; i  )
{
scanf("%d%d%d%d",&q[i].u,&q[i].v,&q[i].w,&q[i].flag);
if(q[i].flag)
q[i].w = 0;
}
sort(q,q A,cmp);
for(i = 0; i < A; i   )
{
int x = find(q[i].u);//兩個端點
int y = find(q[i].v);//找出當前端點所在集合編號
if(x != y)//如果再不同集合,合併
{
bin(x,y);
ans  = q[i].w;
}
}
printf ("%d\n",ans);
}
return 0;
}