Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int totalPlaces, nOfCities, nOfRoads, source, to;
- //first = distance, second.first = capacity, second.second = reached vertex
- vector<vector<pair<int,pair<int,int>>>> graph;
- vector<vector<pair<int,int>>> smallestGraph;
- vector<set<int>> cities;
- vector<bool> visited;
- vector<int> dist;
- vector<pair<int,int>> path;
- bool bfs(vector<vector<int>> residualGraph, int src, int target, int parent[]) {
- visited.clear();
- visited.resize(totalPlaces);
- queue<int> q;
- q.push(src);
- visited[src] = true;
- parent[src] = -1;
- while (!q.empty()) {
- int u = q.front(); q.pop();
- for (int v = 0; v < totalPlaces; v++) {
- if (!visited[v] and residualGraph[u][v] > 0) {
- q.push(v);
- parent[v] = u;
- visited[v] = true;
- }
- }
- }
- return visited[target];
- }
- int fordFulkerson(int src, int target) {
- int u, v;
- vector<vector<int>> residualGraph;
- residualGraph.resize(graph.size());
- for (int i = 0; i < graph.size(); i++) {
- residualGraph[i].resize(graph.size());
- }
- for (int i = 0; i < graph.size(); i++) {
- for (int j = 0; j < graph[i].size(); j++) {
- residualGraph[i][graph[i][j].second.second] = graph[i][j].second.first;
- }
- }
- int parent[totalPlaces];
- int maxFlow = 0;
- while (bfs(residualGraph, src, target, parent)) {
- int pathFlow = INT_MAX;
- for (v = target; v != src; v = parent[v]) {
- u = parent[v];
- pathFlow = min(pathFlow, residualGraph[u][v]);
- }
- for (v = target; v != src; v = parent[v]) {
- u = parent[v];
- residualGraph[u][v] -= pathFlow;
- residualGraph[v][u] += pathFlow;
- }
- maxFlow += pathFlow;
- }
- return maxFlow;
- }
- int dijkstra() {
- path.resize(totalPlaces);
- dist.resize(totalPlaces);
- for (int i = 0; i < totalPlaces; i++) {
- dist[i] = INT_MAX;
- }
- dist[source] = 0;
- priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
- dist[source] = 0;
- pq.push({dist[source], source});
- while (!pq.empty()) {
- int u = pq.top().second;
- pq.pop();
- for (pair<int, pair<int,int>> v : graph[u]) {
- if (dist[u] + v.first < dist[v.second.second]) {
- dist[v.second.second] = dist[u] + v.first;
- path[v.second.second] = {v.second.first, u};
- pq.push({dist[v.second.second], v.second.second});
- }
- }
- }
- return dist[to];
- }
- int main() {
- cin >> totalPlaces >> nOfCities;
- cities.resize(totalPlaces);
- graph.resize(totalPlaces);
- for (int i = 0; i < nOfCities; i++) {
- int v;
- char ch;
- while (1) {
- scanf("%d%c",&v,&ch);
- if (ch == '\n') {
- cities[i].insert(v);
- break;
- }
- cities[i].insert(v);
- }
- }
- cin >> nOfRoads;
- for (int i = 0; i < nOfRoads; i++) {
- int u, v, c, d;
- cin >> u >> v >> c >> d;
- //first = distance, second.first = capacity, second.second = reached vertex
- graph[u].push_back({d, {c, v}});
- }
- cin >> source >> to;
- cout << source << " " << to << endl;
- cout << totalPlaces << " " << nOfCities << endl;
- for (auto x : cities) {
- for (auto y : x) {
- cout << y << " ";
- }
- cout << endl;
- }
- int i = 0;
- for (auto x : graph) {
- cout << "Vertice "<< i++ << ": ";
- for (auto y : x) {
- cout << "(" << y.first << ", " << y.second.first << ", " << y.second.second << ")" << "->";
- }
- cout << endl;
- }
- cout << dijkstra() << endl;
- for (int i = 0; i < path.size(); i++) {
- cout << "(" << i << ", " << path[i].first << ", " << path[i].second << ")" << endl;
- }
- smallestGraph.resize(totalPlaces);
- for (int i = 0; i < path.size(); i++) {
- if (path[i].second == source) {
- smallestGraph[source].push_back({path[i].first, i});
- }
- smallestGraph[path[i].second].push_back({path[i].first, i});
- }
- for (auto x : smallestGraph) {
- for (auto y : x) {
- cout << "(" << y.first << ", " << y.second << ")" << endl;
- }
- cout << endl;
- }
- cout << fordFulkerson(source, to) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement