BOJ)12963 달리기

문제: icpc.me/12963

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

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

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

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

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

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

#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, 0, sizeof(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;
}