사탕 줍는 로봇 - 15892

//15892 - 사탕 줍는 로봇
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int N, M;
typedef struct edge {
    int dest;
    int capa;
    struct edge* rev;
 
    edge(int d, int c) : dest(d), capa(c) {}
}Edge;
 
vector<vector<Edge*>> adj;
int work[301];
int level[301];
 
void init() {
    cin >> N >> M;
    adj = vector<vector<Edge*>>(N+1);
    int x, y, c;
    for(int i = 0; i<M; ++i) {
        cin >> x >> y >> c;
        Edge* u = new Edge(y, c);
        Edge* v = new Edge(x, c);
        u->rev = v;
        v->rev = u;
        adj[x].push_back(u);
        adj[y].push_back(v);
    }
}
 
bool bfs() {
    fill(level, level+N+1, -1);
    queue<int> Q;
    Q.push(1);
    level[1] = 0;
 
    while(!Q.empty()) {
        int here = Q.front();
        Q.pop();
 
        for(int i = 0; i<adj[here].size(); ++i) {
            Edge* e = adj[here][i];
            int there = e->dest;
            int cap = e->capa;
 
            if(level[there] == -1 && cap > 0) {
                level[there] = level[here]+1;
                Q.push(there);
            }
        }
    }
    return level[N] != -1;
}
 
int dfs(int here, int fl) {
 
    if(here == N) return fl;
 
    for(int& i = work[here]; i<adj[here].size(); i++) {
        Edge* e = adj[here][i];
        Edge* re = e->rev;
        int there = e->dest;
        int cap = e->capa;
 
        if(level[there] == level[here] + 1 && cap > 0) {
            int df = dfs(there, min(fl, cap));
 
            if(df > 0) {
                e->capa -= df;
                re->capa += df;
                return df;
            }
        }
    }
    return 0;
}
 
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    init();
    int ans = 0;
    while(bfs()) {
        
        fill(work, work+N+1, 0);
 
        while(1) {
            int df = dfs(1, 11111);
            if(!df) break;
 
            ans += df;
        }
    }
    cout << ans;    
}

 

 

 

 

 

colorscripter.com/info#e"

정보 - Color Scripter

 

 

 

 

 

사탕 줍는 로봇

최대 유량을 구하는 문제입니다. 디닉알고리즘을 사용해서 해결했습니다!