PS와 개발을 공부하자

LR Circulation 예제) Codeforces - Reactor Cooling 본문

Algorithm/Problem Solving

LR Circulation 예제) Codeforces - Reactor Cooling

sgc109 2017. 7. 25. 18:17

http://codeforces.com/gym/100199/attachments


LR Flow 예제.

각각의 간선의 하한 L과 상한 R 이 있을 때 모든 간선의 용량을 R - L 로 주고

가상의 소스를 만들어 각 노드로 들어오는 하한, 즉 demand flow 의 합만큼의 용량의 간선을 이어주고

가상의 싱크를 만들어 각 노드에서 나가는 하한의 합만큼의 용량의 간선을 빼준다.

그 다음 maxflow 를 돌려서 최대 유량이 모든 demand flow의 합과 같다면 feasible 한거고

더 적다면 feasible 하지 않은것이다.


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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
struct Dinic{
    struct edge{
        int to, cap, rev;
    };
    int size, src, sink;
    vector<vector<edge> > G;
    vector<int> level, iter;
    Dinic(){}
    Dinic(int sizeint src, int sink) {
        this->size = size;
        this->src = src;
        this->sink = sink;
        G = vector<vector<edge> >(size);
        level = vector<int>(size-1);
        iter = vector<int>(size0);
    }
    void addEdge(int from, int to, int cap){
        G[from].push_back({to, cap, (int)G[to].size()});
        G[to].push_back({from, 0, (int)G[from].size()-1});
    }
    bool bfs(int src, int sink){
        queue<int> q;
        q.push(src);
        level[src] = 0;
        while(!q.empty() && level[sink] == -1){
            int here = q.front();
            q.pop();
            for(auto e : G[here]){
                if(e.cap <= 0 || level[e.to] != -1continue;
                level[e.to] = level[here] + 1;
                q.push(e.to);
            }
        }
        return level[sink] != -1;
    }
 
    int dfs(int here, int minFlow, int sink){
        if(here == sink) return minFlow;
        for(int& i = iter[here]; i < (int)G[here].size(); i++){
            auto& e = G[here][i];
            if(e.cap == 0 || level[e.to] != level[here] + 1continue;
            int f = dfs(e.to, min(minFlow, e.cap), sink);
            if(f > 0){
                e.cap -= f;
                G[e.to][e.rev].cap += f;
                return f;
            }
        }
        return 0;
    }
    
    int getMaxflow(){
        int ret = 0;
        while(1){
            level = vector<int>(size-1);
            iter = vector<int>(size0);
            if(!bfs(src, sink)) break;
            while(int f = dfs(src, INF, sink)) ret += f;
        }
        return ret;
    }
};
 
struct LRMaxFlow{
    Dinic dinic;
    int size, src, sink, fsrc, fsink;
    vector<int> inSum, outSum;
    LRMaxFlow(int sizeint src, int sink){
        this->size = size;
        this->src = src;
        this->sink = sink;
        fsrc = size;
        fsink = size + 1;
        dinic = Dinic(size + 2, fsrc, fsink);
        inSum = vector<int>(size0);
        outSum = vector<int>(size0);
    }
    void addEdge(int from, int to, int cap, int lower){
        dinic.addEdge(from, to, cap);
        inSum[to] += lower;
        outSum[from] += lower;
    }
    int getMaxflow(){
        for(int i = 0 ; i < size; i++if(inSum[i]) dinic.addEdge(fsrc, i, inSum[i]);
        for(int i = 0 ; i < size; i++if(outSum[i]) dinic.addEdge(i, fsink, outSum[i]);
        dinic.addEdge(sink, src, INF);
        return dinic.getMaxflow();
    }
};
 
int N, M;
int ans[20003];
int id[203][203];
int upper[20003];
int main() {
    freopen("cooling.in""r", stdin);
    freopen("cooling.out""w", stdout);
    fastio();
    for(int i = 0 ; i < 203; i++for(int j = 0 ; j < 203; j++) id[i][j] = 20000;
    cin >> N >> M;
    LRMaxFlow lr(N, 00);
    for(int i = 0 ; i < M; i++) {
        int a, b, l, r;
        cin >> a >> b >> l >> r;
        a--, b--;
        id[a][b] = i;
        lr.addEdge(a, b, r - l, l);
        upper[i] = r;
    }
 
    int ret = lr.getMaxflow();
    int sum = 0;
    for(int i = 0 ; i < N; i++) sum += lr.inSum[i];
    if(sum != ret) return !printf("NO");
    for(int i = 0 ; i < N; i++){
        for(auto e : lr.dinic.G[i]){
            int num = id[i][e.to];
            ans[num] = upper[num] - e.cap;
        }
    }
    cout << "YES\n";
    for(int i = 0 ; i < M; i++cout << ans[i] << "\n";
    return 0;
}
cs


0 Comments
댓글쓰기 폼