[BZOJ 1733] [Usaco2005 feb] Secret Milking Machine 【二分 + 最大流】
题目链接:BZOJ - 1733
题目分析
直接二分这个最大边的边权,然后用最大流判断是否可以有 T 的流量。
代码
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int MaxN = 200 + 5, MaxM = 80000 + 5, INF = 999999999; inline int gmin(int a, int b) {return a < b ? a : b;} inline int gmax(int a, int b) {return a > b ? a : b;} int n, m, Ts, Top, Ans, S, T, Tot; int d[MaxN], Num[MaxN]; struct Edge { int u, v, w, len; Edge *Next, *Other; } E[MaxM * 2], *P = E, *Point[MaxN], *Last[MaxN], *EA[MaxM]; inline void AddEdge(int x, int y, int z) { Edge *Q = ++P; ++P; EA[++Top] = P; P -> u = x; P -> v = y; P -> len = z; P -> Next = Point[x]; Point[x] = P; P -> Other = Q; Q -> u = y; Q -> v = x; Q -> len = z; Q -> Next = Point[y]; Point[y] = Q; Q -> Other = P; } void Set_Edge(int x) { for (int i = 1; i <= Top; ++i) { if (EA[i] -> len <= x) EA[i] -> w = 1; else EA[i] -> w = 0; EA[i] -> Other -> w = 0; } } int DFS(int Now, int Flow) { if (Now == T) return Flow; int ret = 0; for (Edge *j = Last[Now]; j; j = j -> Next) if (j -> w && d[j -> u] == d[j -> v] + 1) { Last[Now] = j; int p = DFS(j -> v, gmin(j -> w, Flow - ret)); j -> w -= p; j -> Other -> w += p; ret += p; if (ret == Flow) return ret; } if (d[S] >= Tot) return ret; if (--Num[d[Now]] == 0) d[S] = Tot; ++Num[++d[Now]]; Last[Now] = Point[Now]; return ret; } bool Check() { int MaxFlow = 0; S = 1; T = n; Tot = n; memset(d, 0, sizeof(d)); memset(Num, 0, sizeof(Num)); Num[0] = Tot; for (int i = 1; i <= Tot; ++i) Last[i] = Point[i]; while (d[S] < Tot) MaxFlow += DFS(S, INF); if (MaxFlow >= Ts) return true; else return false; } int main() { scanf("%d%d%d", &n, &m, &Ts); int a, b, c; int l, r, mid; l = INF; r = -INF; Top = 0; for (int i = 1; i <= m; ++i) { scanf("%d%d%d", &a, &b, &c); AddEdge(a, b, c); AddEdge(b, a, c); l = gmin(l, c); r = gmax(r, c); } while (l <= r) { mid = (l + r) >> 1; Set_Edge(mid); if (Check()) { Ans = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n", Ans); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。