Đề 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
#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;
}
|