Problem: 给了一个源点，一个汇点，一些节点之间的容量，求最大网络流。 Solution: 用dinic求一下即可。
#include<cstdio> #include<iostream> #include<sstream> #include<cstdlib> #include<cmath> #include<cctype> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<set> #include<map> #include<ctime> #include<vector> #include<fstream> #include<list> using namespace std; typedef long long ll; typedef unsigned long long ull; #define ms(s) memset(s,0,sizeof(s)) const double PI = 3.141592653589; const int INF = 0x3fffffff; const int maxn = 200; int G[maxn+5][maxn+5]; int layer[maxn+10]; bool visited[maxn+10]; int n, m; bool count_layer() {//bfs 分层 queue<int> q; q.push(1); memset(layer, -1, sizeof(layer)); layer[1] = 0; while(!q.empty()) { int v = q.front(); q.pop(); for(int i = 1; i <= m; i++) { if(layer[i] == -1 && G[v][i] > 0) { layer[i] = layer[v]+1; if(i == m) return true; q.push(i); } } } return false; } int dinic() { deque<int> dq;//可以通过下标访问的栈 int ans = 0; int s, t, idx, mins; while(count_layer()) {//只要还可以分层 ms(visited); visited[1] = true; dq.push_back(1); while(!dq.empty()) { int v = dq.back(); if(v == m) {//找到一条增广路径 mins = INF; for(int i = 1; i < dq.size(); i++) {//找到最小容量 s = dq[i-1]; t = dq[i]; if(G[s][t] < mins) { mins = G[s][t]; idx = s; } } ans += mins; for(int i = 1; i < dq.size(); i++) {//重建残余网络 s = dq[i-1]; t = dq[i]; G[s][t] -= mins; G[t][s] += mins; } while(!dq.empty() && dq.back() != idx) {//回溯 dq.pop_back(); visited[dq.back()] = false; } } else {//dfs找增广路径 for(int i = 1; i <= m; i++) { if(G[v][i] > 0 && layer[i] == layer[v]+1 && !visited[i]) { dq.push_back(i); visited[i] = true; break; } if(i == m)//回溯 dq.pop_back(); } } } } return ans; } int main() { // freopen("/Users/really/Documents/code/input","r",stdin); // freopen("/Users/really/Documents/code/output","w",stdout); ios::sync_with_stdio(false); int s, e, c; while(cin >> n >> m) { ms(G); for(int i = 0; i < n; i++) { cin >> s >> e >> c; G[s][e] += c; } cout << dinic() << endl; } return 0; }