带有图片例子的 [BLOG]
复杂度是$(n ^ 3)$
HDU3691
// #pragma GCC optimize(2) // #pragma GCC optimize(3) // #pragma GCC optimize(4) #include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> //#include <unordered_set> //#include <unordered_map> // #include<bits/extc++.h> // using namespace __gnu_pbds; using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /**********showtime************/ const int maxn = 502; int mp[maxn][maxn], dis[maxn]; int vis[maxn], bin[maxn]; int n; int concate(int &s, int &t) { memset(dis, 0, sizeof(dis)); memset(vis, 0, sizeof(vis)); int k, maxc, mincut = 0; for(int i=1; i<=n; i++) { k = -1, maxc = -1; for(int j=1; j<=n; j++) { if(bin[j] == 0 && vis[j] == 0 && dis[j] > maxc) { k = j; maxc = dis[j]; } } if(k == -1) return mincut; s = t; t = k; mincut = maxc; vis[k] = 1; for(int j=1; j<=n; j++) { if(vis[j] == 0 && bin[j] == 0) { dis[j] = dis[j] + mp[k][j]; } } } return mincut; } int sw() { int mincut = inf, s, t; for(int i=1; i<n; i++) { int ans = concate(s, t); mincut = min(mincut, ans); bin[t] = 1; if(mincut == 0) return mincut; for(int j=1; j<=n; j++) { if(bin[j] == 0) { mp[s][j] = mp[s][j] + mp[t][j]; mp[j][s] = mp[s][j]; } } } return mincut; } int main(){ int m,s; while(~scanf("%d%d%d", &n, &m, &s) && n + m + s) { for(int i=1; i<=n; i++) { bin[i] = 0; for(int j=1; j<=n; j++) { mp[i][j] = 0; } } for(int i=1; i<=m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); mp[u][v] = mp[u][v] + w; mp[v][u] = mp[u][v]; } printf("%d ", sw()); } return 0; } HDU 3691