• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Apr 25th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <utility>
4. #include <queue>
5. #include <random>
6. #include <algorithm>
7. #include<stack>
8. #include <math.h>
9.
10. const int INF = 2147483645;
11.
12. class ListGraph {
13. public:
14.     ListGraph(int vertices_count);
15.
16.     int VerticesCount() const;
17.
18.     void AddEdge(int from, int to, int weight);
19.
20.     void GetNextVertices(int vertex, std::vector<std::pair<int, int>> &vertices) const;
21.
22. private:
24. };
25.
26. ListGraph::ListGraph(int vertices_count) {
28. }
29.
30. int ListGraph::VerticesCount() const {
32. }
33.
34. void ListGraph::AddEdge(int from, int to, int cap) {
36. }
37.
38. void ListGraph::GetNextVertices(int vertex, std::vector<std::pair<int, int>> &vertices) const {
40. }
41.
42. bool BFS(ListGraph &graph, std::vector<std::vector<int>> &currflow, std::vector<int> &d) {
43.     int N = graph.VerticesCount();
44.     std::queue<int> q;
45.     q.push(0);
46.     d.assign(N,-1);
47.     d[0] = 0;
48.     while (!q.empty()) {
49.         int curr = q.front();
50.         q.pop();
51.         std::vector<std::pair<int, int>> next;
52.         graph.GetNextVertices(curr, next);
53.         for (auto u : next) {
54.             if (d[u.first] == -1 && currflow[curr][u.first] < u.second) {
55.                 q.push(u.first);
56.                 d[u.first] = d[curr] + 1;
57.             }
58.
59.         }
60.     }
61.     return d[N - 1] != -1;
62. }
63. int DFS(int v, int flow, ListGraph &graph, std::vector<int> &ptr, std::vector<std::vector<int>> &currflow,
64.     std::vector<int> &d) {
65.     int N = graph.VerticesCount();
66.     if (v == N - 1 or !flow)
67.         return flow;
68.     std::vector<std::pair<int, int>> next;
69.     graph.GetNextVertices(v, next);
70.     for (; ptr[v] < next.size(); ++ptr[v]) {
71.         int to = next[ptr[v]].first;
72.         int curr_cup = next[ptr[v]].second;
73.         if (d[to] != d[v] + 1)
74.             continue;
75.         int push = DFS(to, std::min(flow, curr_cup - currflow[v][to]), graph, ptr, currflow, d);
76.         if (push != 0) {
77.             currflow[v][to] += push;
78.             currflow[to][v] -= push;
79.             return push;
80.         }
81.
82.     }
83.     return 0;
84. }
85.
86. int Find_max_flow(ListGraph &graph) {
87.     int N = graph.VerticesCount();
88.     int flow = 0;
89.     std::vector<int> ptr(N, 0);
90.     std::vector<int> d(N, -1);
91.     std::vector<std::vector<int>> currflow(N, std::vector<int>(N, 0));
92.
93.     while (true) {
94.         if (!BFS(graph, currflow, d))
95.             break;
96.         ptr.assign(N, 0);
97.         while (int pushed = DFS(0, INF, graph, ptr, currflow, d))
98.             flow += pushed;
99.
100.     }
101.     return flow;
102. }
103.
104. int main() {
105.     int N = 0, M = 0, from = 0, to = 0, cap = 0;
106.     std::cin >> N >> M;
107.     ListGraph graph(N);
108.     for (int i = 0; i < M; ++i) {
109.         std::cin >> from >> to >> cap;
110.         graph.AddEdge(from - 1, to - 1, cap);
111.     }
112.     int ans = Find_max_flow(graph);
113.     std::cout << ans;
114.     return 0;
115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top