데이터 구조 - 원활 한 공사 의 최저 원가 건설 문제

1625 단어

7-2 원활 한 공사 의 최저 원가 건설 문제 (30 분)
한 지역 은 도시 교통 상황 에 대한 조 사 를 통 해 기 존의 도시 간 고속도로 에 대한 통계 데 이 터 를 얻 고 '원활 한 공사' 의 목 표를 제시 했다. 전체 지역 의 모든 두 도시 간 에 신속 한 교통 을 실현 할 수 있 도록 하 는 것 이다 (그러나 직접적인 고속도로 가 연결 되 는 것 이 아니 라 서로 간접 적 으로 빠 른 길 을 통 해 도달 하면 된다).현재 도시 도로 통계 표를 얻 었 는데 표 에는 고속도로 로 건설 할 수 있 는 몇 개의 도로 의 원 가 를 열거 하고 원활 한 공사 에 필요 한 최저 원 가 를 구 했다.
입력 형식:
입력 한 첫 줄 은 도시 수 N 을 드 립 니 다. (1
출력 형식:
원활 한 프로젝트 를 출력 하 는 데 필요 한 최소 비용 입 니 다. 입력 데이터 가 원활 하지 않 으 면 "Impossible" 을 출력 합 니 다.
입력 예시 1:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

출력 예시 1:
12

입력 예시 2:
5 4
1 2 1
2 3 2
3 1 3
4 5 4

출력 예시 2:
Impossible

 이 문 제 는 원활 한 공사 라 는 문제 의 사상 과 대체적으로 일치 합 니 다. 마찬가지 로 원활 한 공사 에서 사용 하 는 두 가지 알고리즘 을 사용 하 는 것 입 니 다. 다만 impossible 의 제한 을 추 가 했 을 뿐 입 니 다. 이 럴 때 우 리 는 알고리즘 에 대해 반드시 모색 하고 이해 하여 우리 의 문제 에 적합 하도록 해 야 합 니 다.
원활 한 프로젝트 코드 에서 우 리 는 used 배열 을 이용 하여 모든 점 을 저장 하 는 지 여 부 를 기록 할 수 있 습 니 다. 그러면 이때 우 리 는 used 배열 로 모든 점 이 연결 되 었 는 지 여 부 를 판단 할 수 있 습 니 다. 그렇지 않 으 면 imposible 을 출력 할 수 있 습 니 다.
 
다음은 AC 코드 를 드 립 니 다.
#include 

using namespace std;
const int maxn=1000+10;
const int INF=0x3f3f3f3f;


int cost[maxn][maxn];
int mincost[maxn];
bool used[maxn];
int V,E;

void prim()
{
    memset(mincost,INF,sizeof(mincost));
    memset(used,false,sizeof(used));

    mincost[1]=0;
    int res=0;
    bool flag=false;

    while(true)
    {
        int v=-1;
        //cout<

iOS 버 전 번호 관리
Redux[2021.09.17]

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage