[hdu]계속 원활 한 공사
2580 단어 최소 생 성 트 리
Problem Description
성 정부의'원활 한 공사'목 표 는 성 전체의 어느 두 마을 간 에 도 도로 교통 을 실현 할 수 있 도록 하 는 것 이다.현재 도시 도로 통계 표를 얻 었 는데 표 에는 임의의 두 도시 간 에 도 로 를 건설 하 는 비용 과 이 도로 가 이미 뚫 렸 는 지 의 상태 가 열거 되 어 있다.지금 당신 이 프로그램 을 작성 하여 성 전체 가 원활 하 게 통 하 는 데 필요 한 최저 원 가 를 계산 해 주 십시오.
Input
테스트 입력 은 약간의 테스트 용례 를 포함한다.각 테스트 용례 의 첫 번 째 줄 은 마을 수 N(1
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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1875 는 최소 생 성 트 리 입 니 다.그들 이 다른 작은 섬 에 가 고 싶 을 때 작은 배 를 저어 이 루어 져 야 합 니 다.현재 정 부 는 백도 호 를 대대적으로 발전 시 키 기로 결정 했다. 조건 에 맞 는 다 는 것 은 작은 섬 2 곳 사이 의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.