Advertisement
Josif_tepe

Untitled

Sep 23rd, 2024
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.07 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. const int INF = 2e9;
  6. class Graph {
  7. private:
  8.     vector<vector<int>> adj_matrix;
  9. public:
  10.     Graph() {
  11.        
  12.     }
  13.     Graph(int n) {
  14.         adj_matrix = vector<vector<int>>(n, vector<int>(n, 0));
  15.     }
  16.     void add_edge(int a, int b, int c) {
  17.         adj_matrix[a][b] = c;
  18.     }
  19.     int get_cell(int i, int j) {
  20.         return adj_matrix[i][j];
  21.     }
  22.     void set_cell(int i, int j, int x) {
  23.         adj_matrix[i][j] = x;
  24.     }
  25. };
  26. class STCut {
  27. private:
  28.     int n;
  29.     int S, T;
  30.     Graph adj, r_graph;
  31. public:
  32.     STCut(int n, int S, int T, Graph adj, Graph r_graph) {
  33.         this->n = n;
  34.         this->S = S;
  35.         this->T = T;
  36.         this->adj = adj;
  37.         this->r_graph = r_graph;
  38.     }
  39.     int bfs(vector<int> & parent) {
  40.         vector<bool> visited(n, false);
  41.        
  42.         queue<int> q;
  43.         q.push(S);
  44.         visited[S] = true;
  45.         parent[S] = -1;
  46.        
  47.         while(!q.empty()) {
  48.             int c = q.front();
  49.             q.pop();
  50.            
  51.             for(int i = 0; i < 30; i++) {
  52.                 if(r_graph.get_cell(c, i) > 0 and !visited[i]) {
  53.                     q.push(i);
  54.                     parent[i] = c;
  55.                     visited[i] = true;
  56.                 }
  57.             }
  58.         }
  59.         if(visited[T]) {
  60.             return true;
  61.         }
  62.         return false;
  63.        
  64.     }
  65.     void dfs(vector<bool> & visited, int node) {
  66.         visited[node] = true;
  67.         for(int i = 0; i < 30; i++) {
  68.             if(r_graph.get_cell(node, i) > 0 and !visited[i]) {
  69.                 dfs(visited, i);
  70.             }
  71.         }
  72.     }
  73.     int min_cut() {
  74.         vector<int> parent(30);
  75.        
  76.         while(bfs(parent)) {
  77.             int path_flow = INF;
  78.             for(int i = T; i != S; i = parent[i]) {
  79.                 int j = parent[i];
  80.                 path_flow = min(path_flow, r_graph.get_cell(j, i));
  81.             }
  82.             for(int i = T; i != S; i = parent[i]) {
  83.                 int j = parent[i];
  84.                 r_graph.set_cell(i, j, r_graph.get_cell(i, j) + path_flow);
  85.                 r_graph.set_cell(j, i, r_graph.get_cell(j, i) - path_flow);
  86.             }
  87.            
  88.         }
  89.         vector<bool> visited(30, false);
  90.         dfs(visited, S);
  91.         int res = 0;
  92.         for(int i = 0; i < 30; i++) {
  93.             for(int j = 0; j < 30; j++) {
  94.                 if(visited[i] and !visited[j] and adj.get_cell(i, j)) {
  95.                     res += adj.get_cell(i, j);
  96.                 }
  97.             }
  98.         }
  99.         return res;
  100.     }
  101. };
  102. int main() {
  103.     int n;
  104.     cin >> n;
  105.     char a, b;
  106.     cin >> a >> b;
  107.     int S = a - 'A';
  108.     int T = b - 'A';
  109.    
  110.     Graph g(30);
  111.     for(int i = 0; i < n; i++) {
  112.         char A, B;
  113.         int c;
  114.         cin >> A >> B >> c;
  115.         int tmp_a = A - 'A';
  116.         int tmp_b = B - 'A';
  117.         g.add_edge(tmp_a, tmp_b, c);
  118.         g.add_edge(tmp_b, tmp_a, c);
  119.        
  120.        
  121.     }
  122.     STCut st(n, S, T, g, g);
  123.     cout << st.min_cut();
  124. }
  125.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement