Đề bài
Cho mạng G có n đỉnh và m cạnh, đỉnh phát là 0, và đỉnh thu là n-1. Hãy tìm luồng f* trong mạng sao cho giá trị val(f*) của luồng f* là lớn nhất.Input
- Dòng đầu tiên chứa 2 số n, m là số đỉnh và số cung trong mạng G.
- M dòng tiếp theo, mỗi dòng là 3 số u, v, c cho biết cung nối từ u đến v có trọng số là c.
Output
- Ghi một số nguyên dương cho biết giá trị luồng cực đại tìm được.
Input | Output |
6 9 1 2 10 1 3 10 2 3 2 2 4 4 2 5 8 3 5 9 4 6 10 5 4 6 5 6 10 | 19 |
Minh họa
Giải
- Source code:
#include<bits/stdc++.h> #include<iostream> using namespace std; using ll = long long; const int maxN = 1001; const int INF = 1e9; // so vo cung const int NULL_INT = -1; int n, m; // n: so dinh, m: so canh int s, t; // s: dinh bat dau, t: dinh ket thuc vector<pair<int, int>> adj[maxN]; int parent[maxN]; int RC[maxN][maxN]; // luu tru cung xuoi, cung nguoc int add_flow; // luu tru gia tri luong cuc dai void inp() { cin >> n >> m; for(int i = 0; i < m; i++) { int x, y, z; cin >> x >> y >> z; adj[x].push_back({y, z}); // Do thi co huong thi comment dong code sau adj[y].push_back({x, z}); // Luu tru gia tri trong so RC[x][y] = z; } } bool bfs(int s, int t, int n) { // Khoi tao memset(parent, NULL_INT, sizeof(parent)); parent[s] = 0; add_flow = INT_MAX; queue<int> q; q.push(s); // Lap while(!q.empty()) { int u = q.front(); // Lay phan tu o dau hang doi q.pop(); // xoa bo phan tu o dau ra khoi hang doi //cout << v << " "; for(auto item: adj[u]) { int v = item.first; // dinh v int w = item.second; // trong so if(parent[v] == NULL_INT && RC[u][v]) { parent[v] = u; // Ghi nhan cha cua v la u add_flow = min(add_flow, RC[u][v]); if(v == t) { // neu lap den dinh ket thuc thi dung vong lap return true; } q.push(v); } } } return false; } // Giai thuat Edmonds_Karp // s: dinh bat dau // t: dinh ket thuc // n: so luong dinh int maxFlow_Edmonds_Karp(int s, int t, int n) { int flow = 0; while(bfs(s, t, n)) { flow += add_flow; int v = t; while(v != s) { int u = parent[v]; RC[v][u] += add_flow; // cung nguoc RC[u][v] -= add_flow; // cung xuoi v = u; } } return flow; } int main() { // Chuyen NHAP, XUAT thanh file freopen("lab_8_1_input.INP", "r", stdin); freopen("lab_8_1_output.OUT", "w", stdout); // INPUT inp(); // OUTPUT int s = 1; int t = n; cout << maxFlow_Edmonds_Karp(s, t, n); return 0; }
Chương trình học
Các bài học
Bài học trước Bài học tiếp theo
Chương trình học
Bao gồm Module, Chương, Bài học, Bài tập, Kiểm tra...Chương trình học
Bài học trước Bài học tiếp theo