必要的注释已经加上了,主要是证明部分,做这题之前要把acwing2188给看懂先
我下面这个代码有1个数据点过不了,TLE了,我不知道问题在哪里,希望有同学可以帮我看一下
/*
* 这题说的是有源点有汇点边的流量有上下界的最大流。
* 那么之前无源汇的图已经做过了,其实有源汇跟无源汇的唯一区别就是源点跟汇点的流入跟流出是不相等的
* 但是可以转换一下,你在汇点跟源点之间连一条边,汇点t到源点s的容量是 + infinity,
准确地讲是汇点到源点的容量下界是0,上界是+ infinity。这样就跟无源汇是相同的了。
* 很明显这样得到的无源汇的图G1上面的流跟原图G的流是一一对应的吧。
* 那上题我们讲过了,你构造一个G1'的话无源汇的可行流跟G1'上的满流是一一对应的,至于G1'怎么构造就是上一题的事情了,不在这里赘述。
* 直接告诉你做法再来证明做法的正确性吧,首先我们以G1'中的S为源点,T为汇点求最大流。
* 如果满流存在的话说明原问题存在可行流嘛,然后我们知道G1'中的t -> s也有一条边,下界是0,上界是+ infinity
* 在以S为源点T为汇点求完最大流之后这条t -> s的边上面肯定也有流量,假设是res1吧。
* 然后把这条t -> s的边去掉,得到的图是G1''我们再在G1''上以s为源点t为汇点求最大流,假设得到的结果是res2
* res1 + res2就是我们要的G中s到t的最大流。
* 为什么是正确的呢?
* 假设我们在G1'上面得到的满流是f'
* 然后G上面的另外一个可行流失f,那我们知道f稍微改一下就可以变成G1里面的可行流了吧,你只要在G1的t -> s那条边上
* 加上|f|就可以了,所以不妨还是把这个流称为f吧
* 那么f在G1'里面就有一个对应的满流f1'
* f1' - f'是G1'里面的可行流吗?当然是的吧。
* f1'(u, V') = 0 for all u != S or T,and f'(u, V') = 0 for all u != S or T
* 因为他们都是可行流,因此有f1'(u, V') - f'(u, V') = 0 for all u != S or T
* V' = V ∪ {S, T}
* 这就证明完了进出流守恒吧。接下来证明容量限制
* 这个也挺好证明的嘛,如果(u, v)这条边在原图里存在
* 也就是说cupper(u, v) > 0的话,我们就有
* f1'(u, v) = f1(u, v) - clower(u, v) <= cupper(u, v) - clower(u, v)
* f'(u, v) = f(u, v) - clower(u,v) <= cupper(u, v) - clower(u, v)
* 于是我们知道 cupper(u, v) - clower(u, v) >= f1'(u, v) - f'(u, v) >= clower(u, v) - cupper(u, v)
* 这就有容量限制成立了吧,当然了f1'(u, v) - f'(u, v) = clower(u, v) - cupper(u, v)也是可以的
* 说明是反过来从v流到u了呗。
* 当然了上面这个讨论都是在u跟v都不是S或T的情况下进行的
* 那么如果有一个是S(有一个是T也是同理的),其实更简单了吧
* f1'(S, u) - f'(S, u) = 0的吧,谁让f1'跟f'都是G1'上的满流呢,那肯定符合容量限制的嘛。
* 所以我们就知道了f1' - f'是G1'里面的可行流。
* 而且这个时候你如果吧G1'里面t -> s的边去掉,f1' - f'也做出相应的变化,就可以得到一个s -> t的可行流了吧
* 这很显然的嘛,原来就可行的,说明所有的点容量进出守恒,也符合容量限制,去掉这么一条边
* 受到影响的只有s跟t,他们会变得容量进出不守恒,那就让他们当源点跟汇点不就好了。
* 于是我们就得到了,你任取一个G上的可行流f,会有一个G1'上的从s到t的可行流f1' - f'与之对应
* 那反过来呢?你在G1'上的从s到t的可行流会跟G上的可行流对应吗?
* 首先我们知道,G1'上的从s到t的可行流是绝对不会有流量流到S的,因为当初构造的时候就只有S流到其他点的份
* 同理也不可能有流量流到T,因为此时s是源点,t是汇点,所以T不可以有流量积累,而当初构造时T无法流到其他点。
* 这就使得s到t的可行流ff中不会有流量流到T,因为一旦过去就出不来了,会有积累的。
* 那么问题来了,如果我把f'加到ff上面还会是可行流吗?
* 首先进出量守恒是没问题的,因为ff是s到t的可行流嘛,所以你在t -> s这条边上加上|ff|就可以了,这个是小细节。
* 然后其他的点也是进出量守恒的。但问题是,容量限制满足吗?
* 万一有ff(u, v) = cupper(u, v) - clower(u, v)并且f'(u, v) > 0怎么办?
* 讨论变得困难了,甚至进行不下去的感觉。
* 这就是为什么我要先以S为源点T为汇点做一遍dinic,再以s为源点,t为汇点做dinic
* 当我们以s为源点,t为汇点做的时候手头有的其实是f'这个流玩剩下的。
* 但是无所谓呀,从这个“玩剩下的”出发还是可以得到最大流的嘛,这就是最大流里面很有趣的一个地方了,
* 你从不同的地方出发,最后殊途同归。(因为是不是最大流是由是否有增广路径决定的,不是由你从哪个可行流出发决定的)那么我们就知道了,既然是f'玩剩下的,
* 所以你以s为源点,t为汇点做dinic找增广路的话,是不可能把原先已经满了的边再增广的。
* 因此我们知道ff + f'应该还是一个可行的满流。于是就对应到了原图中的一个可行流,而且肯定是最大流了。
* 因为如果还可以再大的话就把这个流拿过来减去f',又得到一个从s到t的更大的流,就跟原来ff是最大流矛盾了。
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 300, M = 10100 << 1;
int fi[N], ne[M], en[M], w[M], idx = 0;
int n, m, s, t, S, T;
int d[N], cur[N], q[N], A[N], B[N];
struct edge {
int a, b, c, d;
}e[M];
void add(int a, int b, int c) {
idx++;
ne[idx] = fi[a];
fi[a] = idx;
en[idx] = b;
w[idx] = c;
}
bool bfs(int source, int tank) {
int head = 1, tail = 0;
q[++tail] = source, cur[source] = fi[source];
for (int i = 0; i <= n + 1; i++) d[i] = -1;
d[source] = 0;
while (tail - head + 1 > 0) {
int u = q[head++];
for (int p = fi[u]; p > 0; p = ne[p]) {
int v = en[p];
if (d[v] != -1 || !w[p]) continue;
d[v] = d[u] + 1, cur[v] = fi[v], q[++tail] = v;
if (v == tank) return true;
}
}
return false;
}
int find(int u, int minw, int tank) {
if (u == tank) return minw;
for (int p = cur[u]; p > 0; p = ne[p]) {
int v = en[p];
if (d[v] != d[u] + 1 || !w[p]) continue;
int res = find(v, min(minw, w[p]), tank);
if (res == 0) { cur[u] = ne[p]; continue; }
w[p] -= res;
if (p % 2 == 0) w[p - 1] += res;
else w[p + 1] += res;
return res;
}
return 0;
}
int dinic(int source, int tank) {
int r = 0, flow;
while (bfs(source, tank)) {
while (true) {
flow = find(source, 1e8, tank);
if (flow == 0) break;
r += flow;
}
}
return r;
}
int main() {
scanf_s("%d%d%d%d", &n, &m, &s, &t);
int tot = 0;
for (int i = 1; i <= m; i++) {
scanf_s("%d%d%d%d", &e[i].a, &e[i].b, &e[i].c, &e[i].d);
A[e[i].b] += e[i].c, B[e[i].a] += e[i].c;
// 所以看到这里就明白A[u]存的应该是所有到u的边的流量的下界求和
// B[u]存的是所有从u出去的边的流量的下界求和
}
S = 0, T = n + 1;
for (int i = 1; i <= m; i++) {
int a = e[i].a, b = e[i].b, c = e[i].c, d = e[i].d;
add(a, b, d - c); add(b, a, 0);
}
add(t, s, 1e8), add(s, t, 0);
for (int i = 1; i <= n; i++) {
if (A[i] - B[i] == 0) continue;
else if (A[i] > B[i]) add(S, i, A[i] - B[i]), add(i, S, 0), tot += A[i] - B[i];
else add(i, T, B[i] - A[i]), add(T, i, 0);
}
int res = dinic(S, T);
if (res != tot) {
printf_s("%s\n", "No Solution"); return 0;
}
res = w[2 * m + 2];
w[2 * m + 1] = 0, w[2 * m + 2] = 0;
res = res + dinic(s, t);
printf_s("%d\n", res);
}
// 上面这个代码正确性应该是没问题了,11个数据点过了10个,最后一个点TLE了我就不知道是为什么了
// 原本我以为是增广路径的深搜那里出了问题,但是我改过之后还是TLE,我之后再看看吧。
// 我得首先把这道题还有之前的Acwing2188给整理一下先,证明一下做法的正确性。2021年8月19日10:12:38