Advertisement
Guest User

Untitled

a guest
Jul 23rd, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.46 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int totalPlaces, nOfCities, nOfRoads, source, to;
  6. //first = distance, second.first = capacity, second.second = reached vertex
  7. vector<vector<pair<int,pair<int,int>>>> graph;
  8. vector<vector<pair<int,int>>> smallestGraph;
  9. vector<set<int>> cities;
  10. vector<bool> visited;
  11. vector<int> dist;
  12. vector<pair<int,int>> path;
  13.  
  14. bool bfs(vector<vector<int>> residualGraph, int src, int target, int parent[]) {
  15.     visited.clear();
  16.     visited.resize(totalPlaces);
  17.     queue<int> q;
  18.     q.push(src);
  19.     visited[src] = true;
  20.     parent[src] = -1;
  21.     while (!q.empty()) {
  22.         int u = q.front(); q.pop();
  23.         for (int v = 0; v < totalPlaces; v++) {
  24.             if (!visited[v] and residualGraph[u][v] > 0) {
  25.                 q.push(v);
  26.                 parent[v] = u;
  27.                 visited[v] = true;
  28.             }
  29.         }
  30.     }
  31.     return visited[target];
  32. }
  33.  
  34. int fordFulkerson(int src, int target) {
  35.     int u, v;
  36.     vector<vector<int>> residualGraph;
  37.     residualGraph.resize(graph.size());
  38.     for (int i = 0; i < graph.size(); i++) {
  39.         residualGraph[i].resize(graph.size());
  40.     }
  41.     for (int i = 0; i < graph.size(); i++) {
  42.         for (int j = 0; j < graph[i].size(); j++) {
  43.             residualGraph[i][graph[i][j].second.second] = graph[i][j].second.first;
  44.         }
  45.     }
  46.     int parent[totalPlaces];
  47.     int maxFlow = 0;
  48.     while (bfs(residualGraph, src, target, parent)) {
  49.         int pathFlow = INT_MAX;
  50.         for (v = target; v != src; v = parent[v]) {
  51.             u = parent[v];
  52.             pathFlow = min(pathFlow, residualGraph[u][v]);
  53.         }
  54.         for (v = target; v != src; v = parent[v]) {
  55.             u = parent[v];
  56.             residualGraph[u][v] -= pathFlow;
  57.             residualGraph[v][u] += pathFlow;
  58.         }
  59.         maxFlow += pathFlow;
  60.     }
  61.     return maxFlow;
  62. }
  63.  
  64. int dijkstra() {
  65.     path.resize(totalPlaces);
  66.     dist.resize(totalPlaces);
  67.     for (int i = 0; i < totalPlaces; i++) {
  68.         dist[i] = INT_MAX;
  69.     }
  70.     dist[source] = 0;
  71.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  72.     dist[source] = 0;
  73.     pq.push({dist[source], source});
  74.     while (!pq.empty()) {
  75.         int u = pq.top().second;
  76.         pq.pop();
  77.         for (pair<int, pair<int,int>> v : graph[u]) {
  78.             if (dist[u] + v.first < dist[v.second.second]) {
  79.                 dist[v.second.second] = dist[u] + v.first;
  80.                 path[v.second.second] = {v.second.first, u};
  81.                 pq.push({dist[v.second.second], v.second.second});
  82.             }
  83.         }
  84.     }
  85.     return dist[to];
  86. }
  87.  
  88. int main() {
  89.     cin >> totalPlaces >> nOfCities;
  90.     cities.resize(totalPlaces);
  91.     graph.resize(totalPlaces);
  92.     for (int i = 0; i < nOfCities; i++) {
  93.         int v;
  94.         char ch;
  95.         while (1) {
  96.             scanf("%d%c",&v,&ch);
  97.             if (ch == '\n') {
  98.                 cities[i].insert(v);
  99.                 break;
  100.             }
  101.             cities[i].insert(v);
  102.         }
  103.     }
  104.     cin >> nOfRoads;
  105.     for (int i = 0; i < nOfRoads; i++) {
  106.         int u, v, c, d;
  107.         cin >> u >> v >> c >> d;
  108.         //first = distance, second.first = capacity, second.second = reached vertex
  109.         graph[u].push_back({d, {c, v}});
  110.     }
  111.     cin >> source >> to;
  112.     cout << source << " " << to << endl;
  113.     cout << totalPlaces << " " << nOfCities << endl;
  114.     for (auto x : cities) {
  115.         for (auto y : x) {
  116.             cout << y << " ";
  117.         }
  118.         cout << endl;
  119.     }
  120.     int i = 0;
  121.     for (auto x : graph) {
  122.         cout << "Vertice "<< i++ << ": ";
  123.         for (auto y : x) {
  124.             cout << "(" << y.first << ", " << y.second.first << ", " << y.second.second << ")" << "->";
  125.         }
  126.         cout << endl;
  127.     }
  128.     cout << dijkstra() << endl;
  129.     for (int i = 0; i < path.size(); i++) {
  130.         cout << "(" << i << ", " << path[i].first << ", " << path[i].second <<  ")" << endl;
  131.     }
  132.     smallestGraph.resize(totalPlaces);
  133.     for (int i = 0; i < path.size(); i++) {
  134.         if (path[i].second == source) {
  135.             smallestGraph[source].push_back({path[i].first, i});
  136.         }
  137.         smallestGraph[path[i].second].push_back({path[i].first, i});
  138.     }
  139.     for (auto x : smallestGraph) {
  140.         for (auto y : x) {
  141.             cout << "(" << y.first << ", " << y.second << ")" << endl;
  142.         }
  143.         cout << endl;
  144.     }
  145.     cout << fordFulkerson(source, to) << endl;
  146.     return 0;
  147. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement