Advertisement
Josif_tepe

Untitled

May 15th, 2024
756
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int maxn = 100;
  5. int n, m;
  6. int graph[maxn][maxn];
  7. bool bfs(vector<vector<int>> & r_graph, int S, int E, vector<int> & parent) {
  8.     vector<bool> visited(n + 1, false);
  9.     visited[S] = true;
  10.     queue<int> q;
  11.     q.push(S);
  12.     parent[S] = -1;
  13.  
  14.     while(!q.empty()) {
  15.         int node = q.front();
  16.         q.pop();
  17.  
  18.         for(int i = 0; i < n; i++) {
  19.             if(!visited[i] and r_graph[node][i] > 0) {
  20.                 if(i == E) {
  21.                     parent[i] = node;
  22.                     return true;
  23.                 }
  24.                 q.push(i);
  25.                 visited[i] = true;
  26.                 parent[i] = node;
  27.             }
  28.         }
  29.     }
  30.     return false;
  31. }
  32. int max_flow(int S, int E) {
  33.     vector<vector<int>> r_graph(n, vector<int>(n, 0));
  34.     for(int i = 0; i < n; i++) {
  35.         for(int j = 0; j < n; j++) {
  36.             r_graph[i][j] = graph[i][j];
  37.         }
  38.     }
  39.     vector<int> parent(n);
  40.     int res = 0;
  41.     while(bfs(r_graph, S, E, parent)) {
  42.         int path_flow = 2e9;
  43.         for(int i = E; i != S; i = parent[i]) {
  44.             path_flow = min(path_flow, r_graph[parent[i]][i]);
  45.         }
  46.         for(int i = E; i != S; i = parent[i]) {
  47.             r_graph[parent[i]][i] -= path_flow;
  48.             r_graph[i][parent[i]] += path_flow;
  49.         }
  50.         res += path_flow;
  51.     }
  52.     return res;
  53. }
  54. int main() {
  55.     int m;
  56.     cin >> m;
  57.     n = 26;
  58.     for(int i = 0; i < m; i++) {
  59.         char a, b;
  60.         cin >> a >> b;
  61.         int c;
  62.         cin >> c;
  63.  
  64.         graph[a - 'A'][b - 'A'] = c;
  65.     }
  66.     cout << "DA" << endl;
  67.     cout << max_flow(('S' - 'A'), ('T' - 'A')) << endl;
  68.  
  69.  
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement