백준 17726 Inheritance

LeetCode 갤러리
마이너

자동 짤방 이미지

이미지가 없습니다.

자동 짤방으로 사용할 이미지를 등록해 주세요.

Eat, Sleep, LeetCode, Repeat

매니저

부재중입니다.(ddakgun)

부매니저

흑화뉴비(coderhs)

개설일

2022-12-26

꽃지

2023.01.04 02:31:38

조회 57 추천 0 댓글 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#define _DE321BUG
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define all(x) (x).begin(),(x).end() 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
const long double pi = acos(-1.0);
const int INF = 1987654321;
const ll LLINF = 4e18;
const double eps = 1e-9;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//
 
int parent[10002][1002]; // kid/vertice
 
int find(int kid, int n){
    if(parent[kid][n] == -1) return n;
    return parent[kid][n] = find(kid, parent[kid][n]);
}
 
void merge(int kid, int u, int v){
    u = find(kid, u);
    v = find(kid, v);
    if(u == v) return;
    parent[kid][v] = u;
}
 
struct Edge{
    int idx, u, v, weight;
    // bool operator<(const Edge &other) const{
    //     return weight < other.weight;
    // }
    bool operator<(const Edge &other) const{
        return weight > other.weight;
    }
};
 
vector<Edge> edges;
 
int main(){
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif  
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    memset(parent, -1, sizeof(parent));
    
    int N, M, K; cin >> N >> M >> K;
    // if(K > 10){
    //     return 0;
    // }
    for(int i = 1; i <= M; i++){
        int a, b, c; cin >> a >> b >> c;
        edges.push_back({i, a, b, c});
    }
    
    sort(edges.begin(), edges.end());
    // for(auto v : edges){
    //     cout << v.idx << " " << v.u << " " << v.v << " " << v.weight << endl;
    // }
    int ans[300004];
    memset(ans, 0, sizeof(ans));
    for(auto edge : edges){
        // for(int i = 1; i <= K; i++){    
        //     if(find(i, edge.u) == find(i, edge.v)) continue;
        //     merge(i, find(i, edge.u), find(i, edge.v));
        //     ans[edge.idx] = i;
        //     break;
        // }
        bool flag = false;
        int lo = 0;
        int hi = K;
        while(lo + 1 < hi){
            int mid = (lo + hi)/2;
            if(find(mid, edge.u) != find(mid, edge.v)){
                hi = mid;
                flag = true;
            }
            else{
                lo = mid;
            }
        }
        // cout << edge.idx << " " << hi << " " << flag << endl;
        if(find(hi, edge.u) != find(hi, edge.v)){
            merge(hi, find(hi, edge.u), find(hi, edge.v));
            ans[edge.idx] = hi;
        }
        else{
            ans[edge.idx] = 0;
        }
        // if(flag) ans[edge.idx] = K-hi;
        // if(flag) ans[edge.idx] = hi;
        // else ans[edge.idx] = 0;
    }
    for(int i = 1; i <= M; i++) cout << ans[i] << endl;
    
    return 0;
}   
Colored by Color Scripter
cs

https://www.acmicpc.net/problem/17726

문제 설명:

가중치가 C인 양방향 A<->B 그래프. K명이 있을때 1번부터 K번까지 가중치의 합이 가장 크도록 간선들을 선택함. 이 때 선택한 간선들이 사이클을 이루면 안 됨. 1 ~ K번의 사람이 각각 최대로 가져간 간선의 가중치의 합은?

서브태스크 1 :

10명밖에 없기 때문에 모든 간선에 대해 1 ~ 10번까지 크루스칼 알고리즘을 변형해서 최대한 앞 번호한테 주면 됨.

서브태스크 2 :

10000명이나 존재하기 때문에 서브태스크 1의 과정을 O(K) -> O(logK)로 줄여야 됨. 이분탐색을 이용해서 주면 되는데, 임의의 Q가 간선을 가져갈 수 없으면 1 ~ Q-1 모두 가져갈 수 없다는게 그리디하게 증명이 되기 때문에 가능함.

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	2025년 가장 기억에 남는 인터넷 이슈는?	운영자	25/12/22	-	-
85	909. Snakes and Ladders	이벤트ㅇㅅㅇ(219.251)	23.01.24	48	0
83	997. Find the Town Judge	이벤트ㅇㅅㅇ(219.251)	23.01.23	44	0
82	997. Find the Town Judge [1]	개발뉴비	23.01.23	74	0
81	백준 9996번	키비	23.01.23	56	0
78	마갤 입문함 [2]	키비	23.01.22	61	0
77	131. Palindrome Partitioning [1]	개발뉴비	23.01.22	59	0
75	93. Restore IP Addresses [1]	개발뉴비	23.01.21	72	0
74	Longest Palindromic Substring 5번	o오어o(14.37)	23.01.21	30	0
73	Restore IP Addresses 93번	o오어o(14.37)	23.01.21	39	0
72	안녕하세요 오늘부터 릿코 달리게씁니당 [2]	조르디(112.170)	23.01.21	55	0
71	491. Non-decreasing Subsequences [1]	개발뉴비	23.01.21	57	0
70	974. Subarray Sums Divisible by K [1]	개발뉴비	23.01.19	44	0
69	926. Flip String to Monotone Increasing [1]	개발뉴비	23.01.17	43	0
68	57. Insert Interval [1]	개발뉴비	23.01.17	39	0
66	트리 문제 두 개 개빡치네;	개발뉴비	23.01.15	48	0
65	1061. Lexicographically Smallest ~	개발뉴비	23.01.15	42	0
64	여기 갤럼들은 전부 해외취업 준비중? [2]	EvenAsura	23.01.14	107	0
63	1519. Number of Nodes in the Sub-Tree~	개발뉴비	23.01.12	28	0
62	1443. Minimum Time to Collect All Apples	개발뉴비	23.01.11	41	0
59	230111 데일리	꽃지	23.01.11	68	0
58	100. Same Tree	개발뉴비	23.01.10	35	0
56	220110 데일리	꽃지	23.01.10	41	0
53	144. Binary Tree Preorder Traversal	개발뉴비	23.01.09	41	0
52	230109 데일리	꽃지	23.01.09	31	0
51	리트코드 4번 [4]	o오어o(222.121)	23.01.09	66	0
50	리트코드 3번	o오어o(222.121)	23.01.09	25	0
49	220108 데일리	꽃지	23.01.08	55	0
48	68. Text Justification	ㅇㅇ(12.50)	23.01.08	37	0
47	3번문제 코드 딱 한줄만 알려준다	ㅇㅇ(218.234)	23.01.08	38	0
46	코딩 테스트 tdd로 하시는 분 [1]	TS(119.64)	23.01.07	61	0
45	가스스테이션(데일리)	o오어o(222.121)	23.01.07	52	0
44	230107 데일리 [1]	꽃지	23.01.07	55	0
43	134. Gas Station	개발뉴비	23.01.07	47	0
42	1833. Maximum Ice Cream Bars	개발뉴비	23.01.06	58	0
41	230106 데일리	꽃지	23.01.06	50	0
38	오늘의 릿코드 Minimum Number of Arrows~	개발뉴비	23.01.05	41	0
36	230105 데일리 [3]	꽃지	23.01.05	65	0
35	2244. Minimum Rounds 이거 푸는데	TS(119.64)	23.01.05	36	0
34	데일리 문제 어떻게 알아봄...? [1]	TS(119.64)	23.01.05	40	0
33	230104 데일리 [2]	꽃지	23.01.04	87	0
31	Minimum Rounds to Complete All Task [1]	개발뉴비	23.01.04	103	0
30	944. Delete Columns to Make Sorted in TS	ㅇㅇ(119.64)	23.01.04	43	0
	백준 17726 Inheritance	꽃지	23.01.04	57	0
28	백준 14503번 로봇 청소기	개발뉴비	23.01.04	94	0
23	오늘의 릿코드 Delete Columns to Make Sorted [2]	개발뉴비	23.01.03	79	0
22	오늘의 데일리 [3]	꽃지	23.01.03	84	0
19	리트코드 해보면서 느낀 점	ㅇㅇ(119.64)	23.01.03	90	0
18	어쨌든 TS로 대문자 판별하기 문제 풀었는데	ㅇㅇ(119.64)	23.01.03	47	0
17	저는 js로 할게요 [5]	ㅇㅇ(119.64)	23.01.03	80	0
16	오늘의 릿코드 Detect Capital	개발뉴비	23.01.02	61	1