Участник:Andriygav/BANKROB

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/BANKROB/

#include <iostream>
using namespace std;
 
int E, to[2097152], last[2048], next_[2097152], cap[2097152], flow[2097152];
int seen_dfs[2048], seen_bfs[2048], d[2048], q[2048], *head, *tail;
int yes, indeed;
 
void add_edges(int x, int y, int v){
    to[E] = y;
    next_[E] = last[x];
    last[x] = E;
    cap[E] = v;
 
    to[E + 1] = x;
    next_[E + 1] = last[y];
    last[y] = E + 1;
    cap[E + 1] = 0;
 
    flow[E] = 0;
    flow[E + 1] = 0;
    E += 2;
}
 
int bfs(int src, int sink) {
    for(head = tail = q, d[*tail++ = sink] = 0, seen_bfs[sink] = ++yes; head < tail;){
    	int x = *head++;
        for(int i = last[x]; i >= 0; i = next_[i]){
        	int y = to[i];
            if(cap[i^1] > flow[i^1] && seen_bfs[y] != yes){
            	*tail++ = y;
                seen_bfs[y] = yes;
                d[y] = d[x] + 1;
            }
        }
    }
 
    return seen_bfs[src] == yes;
}
 
int dfs(int x, int df, int sink) {
    if(x == sink){ 
        return df;
    }
 
    if(seen_dfs[x] == indeed){
        return 0;
    }
 
    seen_dfs[x] = indeed;
    for(int i = last[x]; i >= 0; i = next_[i]){
    	int y = to[i];
 
        if(seen_bfs[y] == yes && d[y] + 1 == d[x]){
            if(cap[i] > flow[i]){
                int dt = dfs(y, min(cap[i] - flow[i], df), sink);
 
                if (dt != 0) {
                    flow[i] += dt;
                    flow[i^1] -= dt;
                    return dt;
                }
            }
        }
    }
 
    return 0;
}
 
int maxflow(int src, int sink){
    int T = 0, dt;
 
    while(bfs(src, sink)){
        do{
            indeed += 1;
            dt = dfs(src, 1073741824, sink);
            T += dt;
        }while(indeed && dt);
    }
 
    return T;
}
 
int main() {
    int s, t, n, m;
 
    cin >> n >> m;
    cin >> s >> t;
    s--;
    t--;
 
    E = 0;
    for(int i = 0; i < n + n; i++){
    	last[i] = -1;
    }
 
    for(int k = 0; k < m; ++k){
    	int ver1, ver2;
    	cin >> ver1 >> ver2;
    	add_edges(ver1 - 1 + n, ver2 - 1, 1073741824);
    	add_edges(ver2 - 1 + n, ver1 - 1, 1073741824);
    }
 
    for(int i = 0; i < n; i++){
    	add_edges(i, i + n, 1);
    }
 
    cout << maxflow(s + n, t);
    return 0;
}