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);
  12.     void add_edge(int,int,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[0];
  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()){
  131.         graph.add_edge(edges[j],edges[j+1],edges[j+2]);
  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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top