• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Jun 19th, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <algorithm>
3. #include <vector>
4. class Graph{
5. public:
6.     int v_count;// вершины
7.     int **matrix; // матрица смежности
8.     int **flow;
9.     bool *visited;
10.     int *prevs;
11.     Graph(int);
13.     void print_matrix();
14.     ~Graph();
15. };
16.
17. Graph::~Graph(){
18.     for(int i = 0; i < v_count; i++){
19.         delete [] flow[i];
20.         delete [] matrix[i];
21.     }
22.     delete [] flow;
23.     delete [] matrix;
24.     delete [] visited;
25.     delete [] prevs;
26. }
27.
28. void Graph::print_matrix(){
29.     std::cout << "  ";
30.     for (int i = 0; i < v_count; i++) {
31.         std::cout << (char)(i+'a') << " ";
32.     }
33.     std::cout << std::endl;
34.     for(int i = 0; i < v_count; i++){
35.         std::cout << (char)(i+'a') << " ";
36.         for(int j = 0; j < v_count; j++)
37.             std::cout << matrix[i][j] << " ";
38.         std::cout << std::endl;
39.     }
40. }
41.
42. Graph::Graph(int vertex):v_count(vertex){
43.     matrix = new int*[v_count];
44.     flow = new int*[v_count];
45.     visited = new bool[v_count];
46.     prevs = new int[v_count];
47.     for(int i = 0; i < v_count; i++){
48.         visited[i] = false;
49.         prevs[i] = -1;
50.         matrix[i] = new int [v_count];
51.         flow[i] = new int [v_count];
52.         for(int j = 0; j < v_count; j++){
53.             flow[i][j] = 0;
54.             matrix[i][j] = 0;
55.         }
56.     }
57. }
58.
59. void Graph::add_edge(int from, int to, int weight){
60.     matrix[from][to] = weight;
61. }
62.
63. void deepSearch(int num,Graph &graph, int stock){
64.     if(graph.visited[stock])
65.         return;
66.     graph.visited[num] = true;
67.     for (int i = 0; i < graph.v_count; i++){
68.         if (!graph.visited[i] && (graph.matrix[num][i] - graph.flow[num][i] > 0 && graph.matrix[num][i] != 0 || graph.flow[num][i] < 0 && graph.matrix[i][num] != 0)){
69.             graph.prevs[i] = num;
70.             deepSearch(i,graph,stock);
71.         }
72.     }
73. }
74.
75. bool getPath(int istock, int stock,Graph &graph){
76.     deepSearch(istock,graph,stock);
77.     for (int i = 0; i < graph.v_count; i++)
78.         graph.visited[i] = false;
79.     return (graph.prevs[stock] != -1);
80. }
81.
82. int calcFlow(int stock, int istock,Graph &graph){
83.     int maxFlow = 0;
84.     while (getPath(istock, stock,graph)){
85.         int tmp = graph.matrix[graph.prevs[stock]][stock] - graph.flow[graph.prevs[stock]][stock];
86.         for (int num = stock; 0 <= graph.prevs[num]; num = graph.prevs[num])
87.             tmp = std::min(tmp, graph.matrix[graph.prevs[num]][num] - graph.flow[graph.prevs[num]][num]);
88.         for (int num = stock; 0 <= graph.prevs[num]; num = graph.prevs[num]){
89.             graph.flow[graph.prevs[num]][num] += tmp;
90.             graph.flow[num][graph.prevs[num]] -= tmp;
91.         }
92.         maxFlow += tmp;
93.         for (int i = 0; i < graph.v_count; i++)
94.             graph.prevs[i] = -1;
95.     }
96.     return maxFlow;
97. }
98.
99. void printResult(Graph &graph){
100.     for (int i = 0; i < graph.v_count; i++)
101.         for (int j = 0; j < graph.v_count; j++){
102.             if (graph.flow[i][j] != 0 && graph.flow[i][j] < 0)
103.                 graph.flow[i][j] = 0;
104.             if (graph.matrix[i][j] > 0)
105.                 std::cout << (char)(i + '0') << " " << (char)(j + '0') << " " << graph.flow[i][j] << std::endl;
106.         }
107. }
108.
109. int main(){
110.     int  weight, edge_count,max_v;
111.     char stock, source, a, b;
112.     size_t j = 1;
113.     std::vector <int> edges;
114.     edges.push_back(0);
115.     std::cin >> edge_count;
116.     std::cin >> source >> stock;
117.     for (int i = 0; i < edge_count;i++) {
118.         std::cin >> a >> b >> weight;
119.         edges.push_back((int)(a - '0'));
120.         edges.push_back((int)(b - '0'));
121.         edges.push_back(weight);
122.     }
123.     max_v = edges;
124.     for (size_t i = 1; i < edges.size(); i++) {
125.         if(i % 3 == 0)
126.             continue;
127.         max_v = std::max(max_v,edges[i]);
128.     }
129.     Graph graph(max_v+1);
130.     while(j!=edges.size()){
132.         j+=3;
133.     }
134.     //graph.print_matrix();
135.     std::cout << calcFlow((int)(stock - '0'),(int)(source - '0'),graph) << std::endl;
136.     printResult(graph);
137.
138.
139.     return 0;
140. }
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.
Not a member of Pastebin yet?