데이터 구조 - 원활 한 공정 의 부분 적 최소 비용 문제
1422 단어 데이터 구조
한 지역 은 도시 교통 상황 에 대한 조 사 를 통 해 기 존의 도시 간 고속도로 에 대한 통계 데 이 터 를 얻 고 '원활 한 공사' 의 목 표를 제시 했다. 전체 지역 의 모든 두 도시 간 에 신속 한 교통 을 실현 할 수 있 도록 하 는 것 이다 (그러나 직접적인 고속도로 가 연결 되 는 것 이 아니 라 서로 간접 적 으로 빠 른 길 을 통 해 도달 하면 된다).현재 도시 도로 통계 표를 얻 었 는데 표 에는 임의의 두 도시 간 에 고속도 로 를 건설 하 는 비용 과 이 도로 가 이미 뚫 렸 는 지 의 상태 가 열거 되 어 있다.지금 당신 이 프로그램 을 작성 하여 전 지역 이 원활 하 게 통 하 는 데 필요 한 최저 원 가 를 계산 해 주 십시오.
입력 형식:
입력 한 첫 줄 은 마을 수 N 을 드 립 니 다. (1≤N≤100)；이 어 N (N - 1) / 2 행 은 마을 간 도로 의 원가 와 건설 상태 에 대응 했다. 각 줄 에 4 개의 정 수 를 주 었 는데 각각 두 마을 의 번호 (1 번 에서 N 번 까지) 이다. 이 두 마을 간 도로 의 원가 와 건설 상태 - 1 은 이미 건설 되 었 고 0 은 건설 되 지 않 았 음 을 나타 낸다.
출력 형식:
전 성의 원활 한 수출 에 필요 한 최저 비용.
입력 예시:
4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0
출력 예시:
3이것 은 트 리 를 최소 로 생 성 하 는 판 문제 로 Prim 알고리즘 과 Kruskal 알고리즘 을 사용 해도 됩 니 다. Prim 알고리즘 과 Kruskal 알고리즘 을 상세 하 게 풀 수 있 습 니 다.
여기 서 제 가 사용 하 는 것 은 Prim 알고리즘 입 니 다. 코드 가 비교적 짧 기 때 문 입 니 다.
다음은 AC 코드 를 직접 드 립 니 다.
#include
using namespace std;
const int maxn=100+10;
const int INF=0x3f3f3f3f;
int cost[maxn][maxn];
int mincost[maxn];
bool used[maxn];
int V;
int prim()
{
memset(mincost,INF,sizeof(mincost));
memset(used,false,sizeof(used));
mincost[1]=0;
int res=0;
while(true)
{
int v=-1;
//cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
