【LOJ116】【LOJ117】有源汇有上下界最大（小）流

下界最大（小）流"/>

【LOJ116】【LOJ117】有源汇有上下界最大（小）流

Description

Solution

orz YMY

用 S,T S , T $S,T$表示超级源点、超级汇点，用 s,t s , t $s,t$表示源点、汇点。

对于有源汇的可行流，从 t t $t$向s" role="presentation">ss$s$连 +∞ + ∞ $+\infty$的边可转化成无源汇可行流，然后用无源汇的方法解决即可。可行流的大小等于 t t $t$向s" role="presentation">ss$s$连的 +∞ + ∞ $+\infty$边流过的流量。
最大流：将可行流大小加上将 t,s t , s $t,s$之间的 inf i n f $inf$边删去后 s s $s$到t" role="presentation">tt$t$的最大流；
最小流：将可行流大小减去将 t,s t , s $t,s$之间的 inf i n f $inf$边删去后 t t $t$到s" role="presentation">ss$s$的最大流（即最多可以退的流）。

Code

最大流

/************************************************* Au: Hany01* Date: Jul 19th, 2018* Prob: 有源汇上下界最大流* Email: hany01@foxmail* Inst: Yali High School
************************************************/#include<bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int, int> PII;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (1e18)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaiatemplate <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }inline int read() {static int _, __; static char c_;for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);return _ * __;
}const int maxn = 205, maxm = ((int)1e4 + 7 + maxn) << 1;int n, m, S, T, v[maxm], nex[maxm], beg[maxn], e = 1, s, t, lev[maxn];
LL f[maxm], tot, Ans, ind[maxn];struct Edge { int u, v, f1, f2; }E[(int)1e4 + 7];inline void add(int uu, int vv, LL ff, int mk = 1) {v[++ e] = vv, f[e] = ff, nex[e] = beg[uu], beg[uu] = e;if (mk) add(vv, uu, 0, 0);
}inline bool BFS(int S, int T) {static queue<int> q;Set(lev, 0), q.push(S), lev[S] = 1;while (!q.empty()) {int u = q.front(); q.pop();for (register int i = beg[u]; i; i = nex[i]) if (f[i] && !lev[v[i]])lev[v[i]] = lev[u] + 1, q.push(v[i]);}return lev[T];
}int cur[maxn];
LL DFS(int u, int T, LL flow) {if (u == T) return flow;register LL tmp, res = flow;for (register int &i = cur[u]; i; i = nex[i]) {if (!f[i] || lev[v[i]] != lev[u] + 1) continue;tmp = DFS(v[i], T, min(res, f[i]));f[i] -= tmp, f[i ^ 1] += tmp;if (!(res -= tmp)) break;}return flow - res;
}int main()
{
#ifdef hany01File("loj116");
#endifn = read(), m = read(), T = (S = n + 1) + 1, s = read(), t = read();For(i, 1, m)E[i].u = read(), E[i].v = read(), E[i].f1 = read(), E[i].f2 = read(),ind[E[i].v] += E[i].f1, ind[E[i].u] -= E[i].f1, add(E[i].u, E[i].v, E[i].f2 - E[i].f1);For(i, 1, n) if (ind[i] > 0) add(S, i, ind[i]), tot += ind[i]; else add(i, T, -ind[i]);add(t, s, INF);while (BFS(S, T)) Cpy(cur, beg), Ans += DFS(S, T, INF);if (Ans < tot) { puts("please go home to sleep"); return 0; }Ans=f[e], f[e] = f[e ^ 1] = 0;while (BFS(s, t)) Cpy(cur, beg), Ans += DFS(s, t, INF);printf("%lld\n", Ans);return 0;
}
//时光只解催人老，不信多情，长恨离亭，泪滴春衫酒易醒。
//    -- 晏殊《采桑子·时光只解催人老》

最小流

/************************************************* Au: Hany01* Date: Jul 19th, 2018* Prob: 有源汇上下界最小流* Email: hany01@foxmail* Inst: Yali High School
************************************************/#include<bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int, int> PII;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (1e18)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaiatemplate <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }inline int read() {static int _, __; static char c_;for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);return _ * __;
}const int maxn = 5e4 + 7, maxm = (125005 + maxn) << 1;int n, m, S, T, v[maxm], nex[maxm], beg[maxn], e = 1, s, t, lev[maxn];
LL f[maxm], tot, Ans, ind[maxn];struct Edge { int u, v, f1, f2; }E[125005];inline void add(int uu, int vv, LL ff, int mk = 1) {v[++ e] = vv, f[e] = ff, nex[e] = beg[uu], beg[uu] = e;if (mk) add(vv, uu, 0, 0);
}inline bool BFS(int S, int T) {static queue<int> q;Set(lev, 0), q.push(S), lev[S] = 1;while (!q.empty()) {int u = q.front(); q.pop();for (register int i = beg[u]; i; i = nex[i]) if (f[i] && !lev[v[i]])lev[v[i]] = lev[u] + 1, q.push(v[i]);}return lev[T];
}int cur[maxn];
LL DFS(int u, int T, LL flow) {if (u == T) return flow;register LL tmp, res = flow;for (register int &i = cur[u]; i; i = nex[i]) {if (!f[i] || lev[v[i]] != lev[u] + 1) continue;tmp = DFS(v[i], T, min(res, f[i]));f[i] -= tmp, f[i ^ 1] += tmp;if (!(res -= tmp)) break;}return flow - res;
}int main()
{
#ifdef hany01File("loj117");
#endifn = read(), m = read(), T = (S = n + 1) + 1, s = read(), t = read();For(i, 1, m)E[i].u = read(), E[i].v = read(), E[i].f1 = read(), E[i].f2 = read(),ind[E[i].v] += E[i].f1, ind[E[i].u] -= E[i].f1, add(E[i].u, E[i].v, E[i].f2 - E[i].f1);For(i, 1, n) if (ind[i] > 0) add(S, i, ind[i]), tot += ind[i]; else add(i, T, -ind[i]);add(t, s, INF);while (BFS(S, T)) Cpy(cur, beg), Ans += DFS(S, T, INF);if (Ans < tot) { puts("please go home to sleep"); return 0; }Ans=f[e], f[e] = f[e ^ 1] = 0;while (BFS(t, s)) Cpy(cur, beg), Ans -= DFS(t, s, INF);printf("%lld\n", Ans);return 0;
}
//溪深难受雪，山冻不流云。
//    -- 洪升《雪望》