본문 바로가기

알고리즘 관련/BOJ

BOJ)12963 달리기

문제: icpc.me/12963


N개의 정점과 M개의 간선으로 이루어진 그래프에서 0번정점에서 N-1번 정점으로 이동 가능한 사람의 최대 수를 구하는 문제이다.


얼핏보면 그냥 0번 정점에서 N-1번 정점으로의 maximum flow를 구하는 문제로 볼 수 있겠지만 한가지 문제가 있다.


간선의 capacity가 너무 커지기 때문에 modulo작업이 필수가 되는데 이와 같은 환경에서 maximum flow를 잘 처리해줄 수가 없기 때문이다.


따라서 우리는 조금 그리디하게 접근을 해야한다.


그래프에서 가장 큰 간선의 가중치는 나머지 모든 간선의 가중치의 합보다 크기 때문에 그 간선으로 이동가능한 경우가 그리디하게 최대가 된다.


그렇기 때문에 그 간선을 연결해보고 0에서 N-1 정점으로 이동가능하면 그 가중치만큼을 더해준 뒤 간선을 제거하고 다음 간선을 확인 만약 연결해도 이동이 안된다면 간선을 유지한채로 다음간선을 확인해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
ll n, m, visited[2020], x, y, r, g[2020];
const ll MOD = (1e9 + 7LL);
vector<vector<ll>> vt;
vector<pair<ll, ll>> edge;
bool dfs(int here) {
    visited[here] = true;
    if (here == n - 1)return true;
    bool ret = false;
    for (auto next : vt[here]) {
        if (!visited[next])
            ret |= dfs(next);
    }
    return ret;
}
int main() {
    scanf("%lld%lld"&n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%lld%lld"&x, &y);
        edge.push_back({ x,y });
        if (!i)g[i] = 1;
        else {
            g[i] = g[i - 1* 3;
            g[i] %= MOD;
        }
    }
    vt.resize(n);
    for (int i = m - 1; i >= 0; i--) {
        memset(visited, 0sizeof(visited));
        vt[edge[i].first].push_back(edge[i].second);
        vt[edge[i].second].push_back(edge[i].first);
        if (dfs(0)) {
            vt[edge[i].first].pop_back();
            vt[edge[i].second].pop_back();
            r += g[i];
            r %= MOD;
        }
    }
    printf("%d\n", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)12869 뮤탈리스크  (0) 2017.06.18
BOJ)12922 블럭 퍼즐  (0) 2017.06.15
BOJ)8217 유성  (1) 2017.06.14
BOJ)14434 놀이기구1  (0) 2017.06.14
BOJ)1396 크루스칼의 공  (3) 2017.06.13