| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 93 | 36 | 33 | 37.079% |
민영 국가는 $N$개의 섬 도시와 $M$개의 양방향 다리로 이루어져 있으며, 모든 섬 도시는 다리를 통해 직간접적으로 연결되어 있다. 각 섬은 1ドル$번부터 $N$번까지 번호가 매겨져 있고, 각 다리는 1ドル$번부터 $M$번까지 번호가 매겨져 있다. $i(1\le i\le M)$번 다리는 섬 도시 $u_i$와 $v_i$를 연결하며, 초기에는 최대 $w_i$의 하중을 견딜 수 있다.
다리 강화 작업에 사용할 수 있는 예산 $B$가 주어진다. 각 다리는 강화 작업을 할 때마다 $y_i$만큼의 비용을 들여 견딜 수 있는 하중을 $x_i$만큼 증가시킬 수 있다. 다리 강화 작업은 예산을 초과하지 않는 선에서 얼마든지 반복할 수 있고, 다리를 강화하지 않을 수도 있다.
강화 작업이 완료된 이후, 임의의 서로 다른 두 섬 $u,ドル $v$ 사이에서 물건을 배송한다고 생각해 보자. 두 섬을 연결하는 경로상의 다리 중 견딜 수 있는 하중이 가장 낮은 다리의 하중이 배송 상한선이 된다. 가능한 경로가 여러 개라면 배송 상한선이 더 큰 경로를 선택한다. 그때의 배송 상한선을 $f(u,v)$라고 하자.
모든 서로 다른 두 섬 쌍 $(u,v)$에 대해서 $f(u,v)$의 최솟값을 $X$라 하자. 시민들의 불만을 줄이고자 $X$를 가능한 한 크게 하고 싶다. 그러기 위해서는 각 다리에 몇 번의 강화 작업을 수행해야 할까?
첫째 줄에 $N,ドル $M,ドル $B$가 공백으로 구분되어 주어진다. $(2≤N≤50,円 000; N-1≤M≤100,円 000; 1≤B≤1,円 000,円 000)$
둘째 줄부터 $M$개의 줄에 걸쳐 순서대로, $i$번 다리의 정보 $u_i,ドル $v_i,ドル $w_i,ドル $x_i,ドル $y_i$가 공백으로 구분되어 주어진다. $(1\le u_i,v_i\le N, u_i\neq v_i; 1≤w_i,x_i≤100,円 000;1\le y_i\le 10)$
입력으로 주어지는 수는 모두 정수이다.
첫째 줄에 $X$의 최댓값을 출력한다.
둘째 줄부터 $M$개의 줄에 걸쳐, $i+1$번째 줄에 $i$번 다리를 몇 번 강화해야 하는지 출력한다. 정답이 여러 개라면 그중 하나만 출력한다.
3 3 1 1 2 5 1 1 2 3 1 4 1 1 3 3 1 1
5 0 1 0
강화 이전의 $f(1,2) =5,ドル $f(2,3) =3,ドル $f(1,3) =3$이므로 $X$는 3ドル$이다.
2ドル$번째 다리를 1ドル$회 강화하면 $X$는 5ドル$가 된다. 예산 내에서 $X$를 이보다 크게 만드는 경우는 존재하지 않는다.
3 3 1 1 2 5 1 1 2 3 1 4 2 1 3 3 1 1
4 0 0 1
3 3 30 1 2 10 1 1 1 2 1 100 2 3 2 1 100 2
701 1 7 7
두 섬을 연결하는 다리가 여러 개 있을 수도 있다.
University > 충남대학교 > 2025 충남대학교 SW-IT Contest I번