백준17506 주때의 자소서 쓰기

작성일 | In

문제 링크

  • http://icpc.me/17506

사용 알고리즘

  • MCMF

풀이

딱 봐도 MCMF 문제인데 각 문항에는 한 개 이상의 스토리가 들어가야 하며 라는 조건이 상당히 골때립니다. 그래프를 열심히 모델링해줍시다.

각 문항에는 한 개 이상의 스토리가 들어가야 하며 조건이 없는 문제를 먼저 풀어봅시다. (c, d)는 용량이 c, 비용이 d인 간선을 의미합니다.

s, t노드는 소스와 싱크를 의미합니다. a, b, c노드는 자소서의 항목을 의미하고, d노드는 사용하지 않을 스토리들을 버리는 용도로 추가했습니다.
max cost를 구해야 하니까, 모든 비용들에 역수를 취해주고 mcmf를 돌리면 됩니다.

이제, 각 문항에는 한 개 이상의 스토리가 들어가야 하며 조건을 붙여봅시다. a, b, c에 강제로 1씩은 무조건 흘려야 합니다.
먼저 새로운 그래프를 봅시다.

K라는 노드를 새로 만들어서 매우 큰 비용의 용량 3짜리 간선을 추가해줍니다. 충분히 큰 용량을 준다면 mcmf를 돌릴 때 항상 그 간선을 우선적으로 타고 갑니다.
K노드에서는 A, B, C로 각각 용량 1인 간선을 추가해서 A, B, C에 스토리를 하나씩 강제로 보내줍니다.
A, B, C에 하나씩 보냈으므로 소스에서 A, B, C로 가는 간선의 용량은 1 줄여야 합니다.

S에서 K로 가는 간선 때문에 정답보다 3e6만큼 큰 결과가 나오므로, 정답을 출력할 때는 3e6을 빼서 출력하면 됩니다.

LR-Flow(간선의 하한이 있는 플로우)문제도 이런 방식으로 푼다고 합니다.

전체 코드

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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define int long long
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define pb push_back
using namespace std;
//using namespace __gnu_pbds; //ordered_set : find_by_order(order), order_of_key(key)
//using namespace __gnu_cxx; //crope : append(str), substr(s, e), at(idx)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> p;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int di[] = {1, 0, -1, 0, 1, 1, -1, -1}, dj[] = {0, 1, 0, -1, 1, -1, 1, -1};
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) { //ax + by = gcd(a, b)
  ll g = a; x = 1, y = 0;
  if (b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
  return g;
}
ll inv(ll a, ll m){ //return x when ax mod m = 1, fail -> -1
    ll x, y;
    ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return mod(x, m);
}
void finish(){ exit(0); }

const int inf = 1010101;

int c[555][555];
int f[555][555];
int d[555][555];
vector<int> g[555];
const int S = 510, T = 511, K = 512;
const int A = 513, B = 514, C = 515, D = 516;

int n, aa, bb, cc;

void addEdge(int s, int e, int x, int y){
    g[s].pb(e); c[s][e] = x; d[s][e] = -y;
    g[e].pb(s); d[e][s] = y;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> aa >> bb >> cc;
    addEdge(S, K, 3, inf);
    addEdge(S, A, aa-1, 0);
    addEdge(S, B, bb-1, 0);
    addEdge(S, C, cc-1, 0);
    addEdge(S, D, inf, 0);
    addEdge(K, A, 1, 0);
    addEdge(K, B, 1, 0);
    addEdge(K, C, 1, 0);

    for(int i=1; i<=n; i++){
        addEdge(i, T, 1, 0);
        int x, y, z; cin >> x >> y >> z;
        addEdge(A, i, 1, x);
        addEdge(B, i, 1, y);
        addEdge(C, i, 1, z);
        addEdge(D, i, 1, 0);
    }

    int ans = 0;
    while(1){
        int inq[555] = {0}, dist[555], par[555];
        queue<int> q;
        memset(dist, 0x3f, sizeof dist);
        memset(par, -1, sizeof par);
        memset(inq, 0, sizeof inq);

        q.push(S); inq[S] = 1; dist[S] = 0;
        while(q.size()){
            int now = q.front(); q.pop(); inq[now] = 0;
            for(auto nxt : g[now]){
                if(c[now][nxt] - f[now][nxt] > 0 && dist[nxt] > dist[now] + d[now][nxt]){
                    par[nxt] = now; dist[nxt] = dist[now] + d[now][nxt];
                    if(!inq[nxt]){
                        inq[nxt] = 1; q.push(nxt);
                    }
                }
            }
        }
        if(par[T] == -1) break;
        for(int i=T; i!=S; i=par[i]){
            ans += d[par[i]][i];
            f[par[i]][i]++;
            f[i][par[i]]--;
        }
    }

    ans *= -1;
    ans -= 3*inf;
    cout << ans;
}