Q: 网络流如果第一题和第二题就差少数边不一样，就比如说本来(1,2)容量为1，第二问(1,2)容量变成INF，这种情况可以直接在(1,2)间加一条边继续增广来求吗？
A: 可以 就加到残量网络上 就行了
那么费用流可以吗？
我觉得在最大流不变，费用改变的情况下是不可以的，因为
inline ll Dinic(int on) {
ll res = 0, cost = 0;
while (spfa(on)) {
ll flow = dfs(S, inf);
res += flow, cost += flow * dis[T];
}
return cost;
}
发现 \(flow\) 为 \(0\) 时，这里一乘，诶，没了
至于有没有更优美的写法，最近再思考思考这个问题
用一个简便的例子演示一下加到残量网络的操作
int main() {
memset(head, -1, sizeof head);
int n;
S = 10, T = 11;
add(S, 1, 1);
add(S, 2, 1);
add(1, 3, 1);
add(2, 3, 1);
add(3, T, 1);
int m = cnt_edge - 2;
cout << e[m].v << endl;
cout << dinic() << endl;
e[m].w = INF;
cout << dinic() << endl;
}
输出
11
1
1
一开始流量为1，加边后又增广1，如果是统计答案记得要求和，因为每次Dinic返回的是本次增广多出来的流
对于费用流也同样：
signed main() {
S = 10, T = 11;
addflow(S, 1, 1, 1);
addflow(S, 2, 1, 2);
addflow(1, 3, 1, 1);
addflow(2, 3, 1, 2);
addflow(3, T, 1, 1);
int m = cnt_edge - 1;
cout << m << " " << e[m].to << endl;
cout << Dinic(-1) << endl;
e[m].flow = 0x3f3f3f3f;
cout << Dinic(-1) << endl;
}
写的是最大费用流，于是先增广了费用高的那一条，第二次增广了费用小的那一条，因此
output
5
3
最大流完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500 + 5;
const int M = N;
const int INF = 0x3f3f3f3f;
struct edge {
int v, w, to;
} e[M * 2];
int pre[N], cnt_edge, dep[N];
int S, T, z, head[N], sum;
int n, m, q[N], cur[N];
void add(int u, int v, int w) {
e[cnt_edge] = {v, w, head[u]};
head[u] = cnt_edge++;
e[cnt_edge] = {u, 0, head[v]};
head[v] = cnt_edge++;
}
bool bfs() {
for (int i = 0; i <= T; i++) dep[i] = 0;
dep[S] = 1;
int l = 0, r = 1;
q[r] = S;
while (l < r) {
int u = q[++l];
for (int i = head[u]; i != -1; i = e[i].to) {
int v = e[i].v;
if (!dep[v] && e[i].w) dep[v] = dep[u] + 1, q[++r] = v;
}
}
return dep[T];
}
int dfs(int u, int mi) {
int res = 0;
if (mi == 0 || u == T) return mi;
for (int &i = cur[u]; i != -1; i = e[i].to) {
int v = e[i].v;
if (dep[u] + 1 == dep[v] && e[i].w) {
int minn = dfs(v, min(mi - res, e[i].w));
e[i].w -= minn;
e[i ^ 1].w += minn;
res += minn;
if (res == mi) return res;
}
}
if (res == 0) dep[u] = 0;
return res;
}
int dinic() {
ll res = 0;
while (bfs()) {
memcpy(cur, head, sizeof(head));
// cout<<res<<endl;
res += dfs(S, INF);
}
return res;
}
int main() {
memset(head, -1, sizeof head);
int n;
S = 10, T = 11;
add(S, 1, 1);
add(S, 2, 1);
add(1, 3, 1);
add(2, 3, 1);
add(3, T, 1);
int m = cnt_edge - 2;
cout << e[m].v << endl;
cout << dinic() << endl;
e[m].w = INF;
cout << dinic() << endl;
}
费用流完整代码
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <vector>
#define endl '\n'
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define P pair<int, int>
using namespace std;
#define int long long
typedef long long ll;
const int maxn = 20 * 40 * 2 * 2 + 5;
const ll inf = 1e18;
int n1, n2, cnt_edge = 1, S, T;
int a1[maxn], a2[maxn], head[maxn];
ll dis[maxn];
bool vis[maxn];
struct edge {
int to, nxt;
ll flow, cost;
} e[(maxn * maxn) << 2];
inline void add(int u, int v, ll w, ll c) {
e[++cnt_edge].nxt = head[u];
head[u] = cnt_edge;
e[cnt_edge].to = v;
e[cnt_edge].flow = w;
e[cnt_edge].cost = c;
}
inline void addflow(int u, int v, ll w, ll c) {
add(u, v, w, c);
add(v, u, 0, -c);
// if(u + 1 == v)
// cout << "add: "<<u << " " << v << " "<<cnt_edge<<endl;
}
inline bool spfa(int on) {
memset(vis, 0, sizeof(vis));
if (on == 1)
for (int i = 0; i <= T; i++) dis[i] = inf;
else
for (int i = 0; i <= T; i++) dis[i] = -inf;
queue<int> q;
q.push(S);
dis[S] = 0;
vis[S] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
// cout << "->" << y << endl;
if ((on == 1 && e[i].flow && dis[y] > dis[x] + e[i].cost) ||
(on == -1 && e[i].flow && dis[y] < dis[x] + e[i].cost)) {
dis[y] = dis[x] + e[i].cost;
if (!vis[y]) q.push(y), vis[y] = 1;
}
}
}
if (on == 1)
return dis[T] != inf;
else
return dis[T] != -inf;
}
ll dfs(int x, ll lim) {
vis[x] = 1;
if (x == T || lim <= 0) return lim;
ll res = lim;
for (int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if (dis[y] != dis[x] + e[i].cost || e[i].flow <= 0 || vis[y]) continue;
ll tmp = dfs(y, min(res, e[i].flow));
res -= tmp;
e[i].flow -= tmp;
e[i ^ 1].flow += tmp;
if (res <= 0) break;
}
return lim - res;
}
inline ll Dinic(int on) {
ll res = 0, cost = 0;
while (spfa(on)) {
ll flow = dfs(S, inf);
res += flow, cost += flow * dis[T];
// cout << "flow " << flow << " " << dis[T] << endl;
}
return cost;
}
int val[maxn][maxn];
int id(int x, int y, int in) {
return 2 * ((n1 * 2 + x - 2) * (x - 1) / 2 + y - 1) + in;
}
vector<int> edge[3];
//拆点之间的边
//除S T 的相邻的边
// T相邻边
struct debug { int u, v, id1, id2; };
signed main() {
S = 10, T = 11;
addflow(S, 1, 1, 1);
addflow(S, 2, 1, 2);
addflow(1, 3, 1, 1);
addflow(2, 3, 1, 2);
addflow(3, T, 1, 1);
int m = cnt_edge - 1;
// cout << m << " " << e[m].to << endl;
cout << Dinic(-1) << endl;
e[m].flow = 0x3f3f3f3f;
cout << Dinic(-1) << endl;
return 0;
}