바 쁜 도시 [로 곡 P2330]

제목 설명
도시 C 는 매우 바 쁜 대도시 로 도시 안의 도로 가 매우 붐벼 서 시장 은 그 중의 도 로 를 개조 하기 로 결정 했다.도시 C 의 도 로 는 이렇게 분포 되 어 있다. 도시 에는 n 개의 교차로 가 있 고 어떤 교차로 사이 에는 도로 가 연결 되 어 있 으 며 두 개의 교차로 사이 에는 최대 한 개의 도로 가 연결 되 어 있다.이 도 로 는 양 방향 이 고 모든 교차 로 를 직간 접적 으로 연결 했다.모든 도로 에 하나의 가치 가 있 는데 가치 가 작 을 수록 이 도로 가 바 쁠 수록 개조 가 필요 하 다 는 것 을 나타 낸다.그러나 시 정부의 자금 이 제한 되 어 시장 이 개 조 를 원 하 는 길 은 적 을 수록 좋다. 그래서 그 는 다음 과 같은 요 구 를 했다.
1. 개 조 된 그 도 로 는 모든 교차 로 를 직간 접적 으로 연결 할 수 있다.2. 요구 1 을 만족 시 키 는 상황 에서 개 조 된 도 로 는 되도록 적다.3. 요구 1, 2 를 만족 시 키 는 상황 에서 개 조 된 도로 중 가치 가 가장 큰 도로 의 가 치 는 최대한 작다.
임무: 시 기획 국 의 당신 으로서 최선 의 결정 을 내 려 야 합 니 다. 그 도 로 를 선택 하면 건설 되 어야 합 니 다.
입 출력 형식
입력 형식:
첫 번 째 줄 에는 두 개의 정수 n 이 있 는데 m 는 도시 에 n 개의 교차로, m 개의 도로 가 있다 는 것 을 나타 낸다.
다음 m 행 은 모든 도로 에 대한 설명 이다. u, v, c 는 교차로 u 와 v 사이 에 도로 가 연결 되 어 있 고 값 은 c 이다.(1≤n≤300，1≤c≤10000，1≤m≤100000)
출력 형식:
두 개의 정수 s, max 는 당신 이 몇 개의 도 로 를 선 택 했 는 지, 점수 가 가장 큰 도로 의 점수 가 얼마 인지 나타 낸다.
입 출력 샘플
샘플 입력 \ # 1: 복사
4 5 1 2 3 1 4 5 2 4 7 2 3 6 3 4 8
출력 샘플 \ # 1: 복사
3 6
사고 최대 변 권 최소 생 성 트 리, kruskar 로 해결
code

#include
using namespace std;
struct data {
    int x,y,k;
} e[100005];
int n,m,tot,maxn,fa[305];
int find(int x) {
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
bool cmp(data x,data y) {
    return x.k<y.k;
}
int main() {
    for(int i=1; i<=300; i++)
        fa[i]=i;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].k);
    printf("%d ",n-1);
    sort(e+1,e+m+1,cmp);
    for(int i=1; i<=m; i++)
        if(find(e[i].x)!=find(e[i].y)) {
            fa[find(e[i].x)]=find(e[i].y);
            tot++;
            maxn=e[i].k;
            if(tot==n-1)
                break;
        }
    printf("%d",maxn);
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[알고리즘] 최소 신장 트리(MST)

신장트리(Spanning Tree)? 최소신장트리 - MST? MST 알고리즘 그래프 내의 모든 정점을 포함하는 트리 = 그래프의 최소 연결 부분 트리! = 그래프에서 일부 간선을 선택해서 만든 트리 => 그렇기 때...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

바 쁜 도시 [로 곡 P2330]

좋은 웹페이지 즐겨찾기