Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <climits>
- #include <cstring>
- using namespace std;
- int n, s, t;
- int doo[102], part[102], query[102];
- int smegnost[102][102], f[102][102];
- bool bfs() {
- int qh = 0, qt = 0;
- query[qt++] = s;
- memset(doo, -1, n * sizeof doo[0]);
- doo[s] = 0;
- while (qh < qt) {
- int v = query[qh++];
- for (auto i = 0; i < n; ++i)
- if (doo[i] == -1 && f[v][i] < smegnost[v][i]){
- query[qt++] = i;
- doo[i] = doo[v] + 1;
- }
- }
- return doo[t] != -1;
- }
- int dfs (int v, int flow) {
- if (!flow) return 0;
- if (v == t) return flow;
- int x = part[v];
- for (auto i = x; i < n; ++i) {
- if (doo[i] != doo[v] + 1) continue;
- int push = dfs(i, min(flow, smegnost[v][i] - f[v][i]));
- if (push) {
- f[v][i] += push;
- f[i][v] -= push;
- return push;
- }
- }
- return 0;
- }
- int main(){
- ifstream fin("circulation.in");
- ofstream fout("circulation.out");
- int m;
- fin >> n >> m;
- n = n + 1;
- for(auto i = 0; i < m; ++i){
- int x, y, z, q;
- fin >> x >> y >> z >> q;
- if(z == 0)
- smegnost[x][y] = q;
- else{
- smegnost[0][y] = z;
- smegnost[x][n] = z;
- smegnost[x][y] = q - z;
- }
- }
- s = 0; t = n - 1;
- int foo = 0;
- for (;;) {
- if (!bfs()) break;
- memset(part, 0, n * sizeof part[0]);
- while (int push = dfs(s, INT_MAX)) foo += push;
- }
- fout << foo;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement