[hdu]계속 원활 한 공사

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16561    Accepted Submission(s): 7118
Problem Description
성 정부의'원활 한 공사'목 표 는 성 전체의 어느 두 마을 간 에 도 도로 교통 을 실현 할 수 있 도록 하 는 것 이다.현재 도시 도로 통계 표를 얻 었 는데 표 에는 임의의 두 도시 간 에 도 로 를 건설 하 는 비용 과 이 도로 가 이미 뚫 렸 는 지 의 상태 가 열거 되 어 있다.지금 당신 이 프로그램 을 작성 하여 성 전체 가 원활 하 게 통 하 는 데 필요 한 최저 원 가 를 계산 해 주 십시오.
 
Input
테스트 입력 은 약간의 테스트 용례 를 포함한다.각 테스트 용례 의 첫 번 째 줄 은 마을 수 N(1N 이 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 "cstdio"
#include "cstring"
#include "algorithm"
#define maxn 10005
using namespace std;
int parent[maxn]={0};
typedef struct{
	int x;
	int y;
	int spt;
}edg;
edg edge[maxn];
int root(int p)
{
	if(parent[p]==p) return p;
	else parent[p]=root(parent[p]);
}
void merge(int a,int b)
{
	a=root(a);
	b=root(b);
	if(a

좋은 웹페이지 즐겨찾기