- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
设 \(u\) 和 \(v\) 为一张图上的任意两个节点。令 \(c(u, v)\) 为它们之间的边的容量, \(f(u, v)\) 为它们之间的流量,则需要满足以下限制.
对于网络上的任意一点 \(x\) ,流入该节点的流量一定等于流出该节点的容量。特别地,源点 \(s\) 的流入量为 0,汇点 \(t\) 的流出量为 0,当然,源点的流出量一定等于汇点的流入量.
整张网络的流定义为从源点流出的流量总和.
有关于网络流的常见问题有 4 种:
接下来一一介绍一下.
故名思意:整张网络的最大流.
我们定义增广路为:若从 \(s\) 到 \(t\) 的一条路径中,边的所有剩余容量均大于 0,则称这样的一条路径为增广路.
在这里简单介绍两种常用的最大流算法.
全名忘了.
显然,如果图中存在增广路,我们可以让一股流量沿着这条增广路从源点流到汇点.
那么 EK 算法的核心便是:利用 bfs 不断地在网络中寻找出增广路,直到网络中不存在一条增广路为止.
而每一次只要找到一条增广路,就更新路径上每一条边的剩余容量。同时网络的最大流量也会改变.
但值得注意的是,如果增广路上的流为 \(delta\) ,每一次我们不仅要将路径上所有正向边的剩余容量减去 \(delta\) ,还要将所有正向边所对应的反向边的剩余容量加上 \(delta\) .
为什么?
这就不得不提起 反向边 的概念了.
为什么要有这个东西?
这是因为每一条边不一定只在一条增广路中出现,它可能被多条增广路同时包含.
为了寻找出所有增广路,我们要让所有的边有被二次筛选的机会.
而反向边给了它们这个机会。你可以感性地理解为,反向边给了程序一个反悔的机会.
为什么要反悔?
如果找到增广路后直接进行更改,则会影响后续继续寻找增广路,因此产生了反向边.
注意:反向边的初始容量为 0,而且反向边的当前容量其实也可以直接代表这条边的当前流量.
以 网络最大流 为模板给个代码吧.
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
#define int long long
struct Edge {
int to, next, w;
}edge[100005];
int head[10005], cnt = 1, a[1005][1005], aug[1005], pre[1005], ans, s, t;
bool vis[10005];
void add(int u, int v, int w) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].w = w;
head[u] = cnt;
}
int bfs(int x) {
queue<int> q;
q.push(x);
memset(vis, 0, sizeof(vis));
vis[x] = 1;
aug[x] = INT_MAX;
while(!q.empty()) {
int tmp = q.front();
q.pop();
for(int i = head[tmp]; i; i = edge[i].next) {
int to = edge[i].to;
if(vis[to] || edge[i].w <= 0) continue;
vis[to] = 1;
pre[to] = i;
q.push(to);
aug[to] = min(edge[i].w, aug[tmp]);
if(to == t) return 1;
}
}
return 0;
}
void change() {
int now = t;
while(now != s) {
int k = pre[now];
edge[k].w -= aug[t];
edge[k ^ 1].w += aug[t];
now = edge[k ^ 1].to;
}
ans += aug[t];
}
signed main() {
int n, m;
SF("%lld%lld%lld%lld", &n, &m, &s, &t);
for(int i = 1; i <= m; i++) {
int u, v, w;
SF("%lld%lld%lld", &u, &v, &w);
if(a[u][v] == 0) {
add(u, v, w), add(v, u, 0);
a[u][v] = cnt;
}
else edge[a[u][v] - 1].w += w;
}
while(bfs(s) != 0) change();
PF("%lld", ans);
return 0;
}
或许这就是它的全名?
想一想为什么 EK 的效率不如 dinic.
因为 EK 算法找到一条增广路就迫不及待地进行了更新.
那么 dinic 就在它的基础上一次性寻找了多条增广路,再统一进行更新.
如何实现?
对于一个节点 \(x\) ,设 \(d_x\) 表示它的层级。即从 \(s\) 到 \(x\) 最少经过的边的数量。再设 \(x\) 连接的下一个节点为 \(y\) ,如果它们间的 \(c(x, y) > 0\) (即还有剩余容量)时,令 \(d_y = d_x + 1\) .
再用 \(dfs\) 逐层遍历。从 \(s\) 开始向下一层寻找合法的节点(即满足上述关系式),直到找到 \(t\) ,再回溯上来。这样不就一次性寻找并修改了多条增广路的边的容量了吗?
一句话解释,从上一次结束搜索的那条边继续进行搜索.
我认为还是比较容易理解的.
还是以上述模板题目为例给一份代码:
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
#define int long long
struct Edge {
int to, next, w;
}edge[200005];
int head[200005], cnt = 1, d[200005], now[200005]; //now数组就是当前弧优化的数组
void add(int u, int v, int w) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].w = w;
head[u] = cnt;
}
bool bfs(int s, int t) {
queue<int> q;
q.push(s);
memset(d, 0, sizeof(d));
d[s] = 1, now[s] = head[s];
while(!q.empty()) {
int tmp = q.front();
q.pop();
for(int i = head[tmp]; i; i = edge[i].next) {
int to = edge[i].to;
if(d[to] || edge[i].w <= 0) continue;
d[to] = d[tmp] + 1;
now[to] = head[to];
q.push(to);
if(to == t) return true;
}
}
return false;
}
int dinic(int x, int t, int flow) {
if(x == t) return flow;
int rest = flow;
for(int i = now[x]; i && rest; i = edge[i].next) {
int to = edge[i].to;
now[x] = i;
if(d[to] != d[x] + 1 || edge[i].w <= 0) continue;
int k = dinic(to, t, min(rest, edge[i].w));
if(k == 0) d[to] = 0;
edge[i].w -= k;
edge[i ^ 1].w += k;
rest -= k;
}
return flow - rest;
}
int work(int s, int t) {
int ans = 0, delta;
while(bfs(s, t)) {
while(delta = dinic(s, t, INT_MAX)) ans += delta;
}
return ans;
}
signed main() {
int n, m, s, t;
SF("%lld%lld%d%lld", &n, &m, &s, &t);
for(int i = 1; i <= m; i++) {
int u, v, w;
SF("%lld%lld%lld", &u, &v, &w);
add(u, v, w), add(v, u, 0);
}
PF("%lld", work(s, t));
return 0;
}
把一张网络中的所有点分为 2 个点集,设其为 \(S\) 和 \(T\) ,其中源点 \(s \in S\) , \(t \in T\) 。但需满足以下两点.
显然,要满足上面两个条件,我们一定要割掉一些边.
我们就将割掉的边的最小权值和叫做最小割.
怎么求呢?
结论:最小割的值等于最大流的值.
怎么证呢?
这不是显然吗, 这里不再详细证明了,毕竟这玩意儿有点东西。 自己去问度娘.
去上面看吧.
在网络中的每条边上加上费用,设其为 \(w(u, v)\) 。则每次经过 \(u\) 和 \(v\) 之间的边时,需要付出 \(w(u, v)\) 的费用.
从源点 \(s\) 到 汇点 \(t\) 因流过的量所付出的费用称为费用流.
利用 已壮烈牺牲多年的同志 SPFA 来求解.
为什么要用这玩意儿而不用复杂度更加稳定的 Dijkstra 呢?
因为图中有可能存在负环.
当然,存在负环时也是可以跑网络流的,只不过需要涉及到消圈算法,这里先不考虑.
首先我们要把费用当成权值跑一遍 SPFA,拿到到达每个点 \(i\) 的最少费用,设其为 \(dis_i\) .
这里就有一个好处: \(dis\) 数组已经帮助我们分好层了.
因此接下来跑一遍 dinic 就 OK 了.
代码改动不大,这里就先不贴了.
最大流只是限制了边的上界,要是同时限制了下界怎么办呢?
很好理解:没有源点和汇点,但网络中有上下界限制时的一个可行的流.
既然没有源汇点,也就没有最大流一说了.
我们要求的是每条边的流量,使得整张网络平衡,或是报告无解.
建议在读下面的内容时自己拿笔画一画。以便于理解.
首先我们建立一张只有下界的网络,图中所有边都是满流状态.
这张网络很有可能不平衡.
因此我们再建立一张差网络,容量即为上界减去下界之差.
在下界网络中,有点 \(i\) ,设流入它的点的量为 \(in_i\) ,流出它的点的量为 \(out_i\) 。分为 2 种情况考虑.
最后在差网络上跑出最大流,得到每条边的流量,再加上下界网络的流,就可以得到一个可行流了.
肯定有无解的情况.
显然,如果一条边的一端是源点 \(s\) 或是汇点 \(t\) 时,这条边必须满流来维护下界网络的平衡。所以只要这些边中有一条边不满流,则报告无解.
但是在实际操作中,我们并不需要真正地建立下界网络。它的唯一一个作用就是帮助我们得到 \(in_i\) 和 \(out_i\) ,显然我们在输入过程中就可以得到.
以 无源汇上下界可行流 为模板给个代码吧.
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
struct Edge {
int to, next, w;
}edge[200005];
int u[200005], v[200005], in[2000005], out[200005], head[200005], d[200005], now[200005], Min[200005], cnt = 1;
bool vis[200005];
void add(int u, int v, int w) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].w = w;
head[u] = cnt;
}
bool bfs(int s, int t) {
queue<int> q;
q.push(s);
memset(d, 0, sizeof(d));
d[s] = 1, now[s] = head[s];
while(!q.empty()) {
int tmp = q.front();
q.pop();
for(int i = head[tmp]; i; i = edge[i].next) {
int to = edge[i].to;
if(d[to] || edge[i].w <= 0) continue;
d[to] = d[tmp] + 1;
now[to] = head[to];
q.push(to);
if(to == t) return true;
}
}
return false;
}
int dinic(int x, int t, int flow) {
if(x == t) return flow;
int rest = flow, i;
for(i = now[x]; i && rest; i = edge[i].next) {
int to = edge[i].to;
if(d[to] != d[x] + 1 || edge[i].w <= 0) continue;
int k = dinic(to, t, min(rest, edge[i].w));
if(k == 0) d[to] = 0;
edge[i].w -= k;
edge[i ^ 1].w += k;
rest -= k;
}
now[x] = i;
return flow - rest;
}
int work(int s, int t) {
int ans = 0, delta;
while(bfs(s, t)) {
while(delta = dinic(s, t, INT_MAX)) ans += delta;
}
return ans;
}
int main() {
int n, m, sum = 0;
SF("%d%d", &n, &m);
int s = 0, t = n + 1;
for(int i = 1; i <= m; i++) {
int Max;
SF("%d%d%d%d", &u[i], &v[i], &Min[i], &Max);
out[u[i]] += Min[i];
in[v[i]] += Min[i];
add(u[i], v[i], Max - Min[i]), add(v[i], u[i], 0);
}
for(int i = 1; i <= n; i++) {
if(in[i] > out[i]) add(s, i, in[i] - out[i]), add(i, s, 0), sum += in[i] - out[i]; //记录必须要有多少流量从源点 s 流出
else if(out[i] > in[i]) add(i, t, out[i] - in[i]), add(t, i, 0);
}
if(work(s, t) != sum) { //只要不是最大流,一定有边没有满流
PF("NO");
return 0;
}
PF("YES\n");
for(int i = 2; i <= 2 * m; i += 2) PF("%d\n", Min[i / 2] + edge[i ^ 1].w);
return 0;
}
很好理解:有源点和汇点,网络中有上下界限制时的一个可行流.
参照上题,先建立起下界网络和差网络.
可以从汇点 \(t\) 向源点 \(s\) 连一条下界为 0 ,容量无限大的边,就转换成了无源汇上下界可行流.
代码根本没啥改动.
遗憾的是,本题并没有找到模板题.
很好理解:有源点和汇点,网络中有上下界限制时的一个最大流.
参照上题,先求出一个有源汇上下界可行流.
那么这个可行流的值是多少呢?
显然,整张网络的流量一定等于汇点 \(t\) 向源点 \(s\) 流入的量。设该值为 \(index\) .
然后我们删去从 \(t\) 到 \(s\) 的边,再按照常规方法跑出从 \(s\) 到 \(t\) 的最大流 \(MaxFlow\) .
最后的答案即为: \(MaxFlow + index\) .
代码改动显然不大,不放了.
很好理解:有源点和汇点,网络中有上下界限制时的一个最小流.
参照上题.
求出 \(index\) 后,跑出从 \(t\) 到 \(s\) 的最大流 \(MaxFlow\) .
最后的答案即为: \(index - MaxFlow\) .
显然上面2、3、4条都是结论性的东西。证明起来有些晦涩。 可能也没太大必要? 因此就先放结论。以后有机会再来详细聊聊。 说真的,上下界网络流考的不太多。 现阶段就先记结论吧.
传送门 。
Algorithm:最大流 .
基本上算是最大流的板子题.
介绍一种重要思路: 拆点 .
我们要明白拆点的意义究竟何在?
其实拆点就是将点权转化为边权.
拿此题讲,每只奶牛的贡献最多为 1。但它喜欢的食品和饮料不止 1 种.
如果直接用食品连接奶牛,奶牛连接饮料的话,它造成的贡献可能就不为 1 了.
因此,我们应该将奶牛 \(i\) 拆成 \(i_x\) 和 \(i_y\) 。一个用来表示是否得到喜欢的食品,另一个则表示是否得到喜欢的饮料.
做法显然了,超级源点 \(s\) 向第 \(f\) 个食品连接容量为 1 的边,第 \(d\) 个饮料向超级汇点 \(t\) 连接容量为 1 的边.
如果第 \(i\) 只奶牛喜欢第 \(f\) 个食品,就从 \(f\) 向 \(i_x\) 连一条容量为 1 的边.
如果第 \(i\) 只奶牛喜欢第 \(d\) 个饮料,就从 \(i_y\) 向 \(d\) 连一条容量为 1 的边.
当然,每个 \(i_x\) 也要向 \(i_y\) 连一条容量为 1 的边。上面说过每只奶牛的贡献最多为 1,因此容量为 1.
/*
第i个点:i -> max = n
第i个吃: n + i -> max = n + lena
第i个喝:n + lena + i -> max = n + lena + lenb
第i个虚点: n + lena + lenb + i -> max = n + lena + lenb + n
*/
int s = 0, t = 2 * n + lena + lenb + 1;
for(int i = 1; i <= n; i++) {
int len1, len2, x;
SF("%d%d", &len1, &len2);
for(int j = 1; j <= len1; j++) {
SF("%d", &x);
add(n + x, i, 1), add(i, n + x, 0);
}
for(int j = 1; j <= len2; j++) {
SF("%d", &x);
add(n + lena + lenb + i, n + lena + x, 1), add(n + lena + x, n + lena + lenb + i, 0);
}
add(i, n + lena + lenb + i, 1), add(n + lena + lenb + i, i, 0);
}
for(int i = 1; i <= lena; i++) add(s, n + i, 1), add(n + i, s, 0);
for(int i = 1; i <= lenb; i++) add(n + lena + i, t, 1), add(t, n + lena + i, 0);
传送门 。
Algorithm:最大流 .
有难度.
设第 \(i\) 个猪舍中有 \(a_i\) 头猪.
对每个猪舍 \(x\) 分类讨论.
该猪舍第一次被顾客 \(i\) 打开.
这时可以从源点 \(s\) 向 \(i\) 连一条容量为 \(a_x\) 的边。表示第 \(i\) 个顾客最多从该猪舍买走 \(a_x\) 头猪.
该猪舍在被顾客 \(i\) 打开前已经被打开过.
这时猪舍中的猪未知,怎么办呢?
我们设上一位打开该猪舍的顾客为 \(last_x\) .
对 \(last_x\) 打开过的所有猪舍,我们都可以对里面的猪随意操作.
可以理解为, \(last_x\) 和 \(i\) 是好朋友, \(last_x\) 担心自己买完猪后 \(i\) 不够买了,于是把自己能买的猪都买了,在 \(i\) 来的时候送给他了.
所以我们从 \(last_x\) 向 \(i\) 连接一条容量为无限的边,表示 \(last_x\) 可以送给 \(i\) 无限多的猪以至于可满足 \(i\) 的需求.
这样一来,问题就解决了.
当然,如果顾客 \(i\) 计划买 \(x_i\) 头猪,就从 \(i\) 向汇点 \(t\) 连接一条容量为 \(x_i\) 的边。表示他买的猪的数量.
至此,本题结束.
s = 0, t = n + 1;
for(int i = 1; i <= m; i++) SF("%d", &a[i]);
for(int i = 1; i <= n; i++) {
int len, x;
SF("%d", &len);
for(int j = 1; j <= len; j++) {
SF("%d", &x);
if(last[x] == 0) {
last[x] = i;
add(s, i, a[x]), add(i, s, 0);
}
else add(last[x], i, 0x3f3f3f3f), add(i, last[x], 0), last[x] = i;
}
SF("%d", &x);
add(i, t, x), add(t, i, 0);
}
传送门 。
Algorithm:最大流 .
思路倒不难,调试起来有些困难.
在第一张图中,设第 \(i\) 行,第 \(j\) 列的石柱最多能够被跳 \(w_{i, j}\) 次。为了方便,赋予它一个编号 \(k_{i, j}\) .
显然,根据上面拆点的思想,这里需要点权转边权。因此将第 \(i\) 行第 \(j\) 列的石柱拆为 \(k_{i, j, x}\) 和 \(k_{i, j, y}\) ,它们间边权即为 \(w_{i, j}\) .
在第二张图中,如果第 \(i\) 行,第 \(j\) 列上有蜥蜴,就从源点 \(s\) 向 \(k_{i, j, x}\) 连接一条容量为 1 的边。再进一步,如果这只蜥蜴可以直接跳出图外,就从 \(k_{i, j, y}\) 向汇点 \(t\) 连接一条容量为 1 的边.
接下来枚举任意两块石柱。第一块在第 \(i\) 行,第 \(j\) 列,第二块在第 \(l\) 行,第 \(r\) 列。如果他们间的距离足以让蜥蜴跳过,就在 \(k_{i, j, y}\) 和 \(k_{l, r, x}\) 间连接一条容量为 1 的边,表示从第一块跳到第二块。同样,在 \(k_{l, r, x}\) 和 \(k_{i, j, y}\) 间连接一条容量为 1 的边,表示从第二块跳到第一块.
到这里,建图就结束了.
SF("%d%d%d", &n, &m, &Max);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
char c;
cin >> c;
if(c != '0') x[++len] = i, y[len] = j, w[len] = c - '0', k[i][j] = len;
}
}
s = 0, t = 2 * len + 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
char c;
cin >> c;
if(c == 'L') {
sum++;
add(s, k[i][j], 1), add(k[i][j], s, 0);
}
}
}
for(int i = 1; i <= len; i++) {
add(i, i + len, w[i]), add(i + len, i, 0);
for(int j = i + 1; j <= len; j++) {
if(get_dis(x[i], y[i], x[j], y[j]) <= Max * Max) add(i + len, j, 0x3f3f3f3f), add(j, i + len, 0), add(j + len, i, 0x3f3f3f3f), add(i, j + len, 0);
}
}
for(int i = 1; i <= len; i++) {
if(x[i] <= Max || y[i] <= Max || x[i] + Max > n || y[i] + Max > m) add(i + len, t, 0x3f3f3f3f), add(t, i + len, 0);
}
传送门 。
Algorithm:最小割 。
显然,割掉一个点,所有与这个点的相连的边都会一并被删掉.
所以将第 \(i\) 个点拆为 \(i_x\) 和 \(i_y\) .
如果 \(u\) 和 \(v\) 之间有一条无向边,就从 \(u_y\) 向 \(v_x\) 间连一条容量为无限的边。同时也从 \(v_y\) 向 \(u_x\) 间连一条容量为无限的边.
为什么是无限?
因为题目中不让删边,容量设为无限那么最小割一定不会割掉它.
同时,对于任意一个非源点并且非汇点的点 \(i\) ,从 \(i_x\) 向 \(i_y\) 间连一条容量为 1 的边。表示删除该点需要 1 的代价.
为什么要排掉源汇点呢?
如果不排掉的话,最小割就可能会选择割掉 \(s_x\) 和 \(s_y\) 间的边或 \(t_x\) 和 \(t_y\) 间的边。此时满足最小割的定义,会直接返回。但实际上割掉源汇点后图可能还是联通的.
所以干脆就不割,将 \(s_x\) 和 \(s_y\) 间的边和 \(t_x\) 和 \(t_y\) 间的边的容量设为无限.
这样就需要枚举每个源汇点来去最小值才能保证正确性了.
难度不大,能够帮助我们进一步理解拆点的意义.
建图简单,输入很恶心,只给输入的代码.
for(int i = 1; i <= m; i++) {
SF("%s", c + 1);
int lenc = strlen(c + 1);
bool flag = false;
for(int j = 1; j <= lenc; j++) {
int sum = 0, u, v;
bool F = false;
while(c[j] >= '0' && c[j] <= '9') {
F = true;
sum = (sum << 3) + (sum << 1) + (c[j] ^ 48);
j++;
}
if(!F) continue;
sum++;
if(!flag) a[i] = sum, flag = true;
else b[i] = sum;
}
}
传送门 。
Algorithm:最小割 。
为了方便,将所有狼的坐标存储在 \(id1\) 里,羊的坐标存储在 \(id2\) 里,空点的坐标存储在 \(id3\) 里。它们都是 pair 类型的.
对于图中的第 \(i\) 行,第 \(j\) 列,赋予它一个编号 \(num_{i, j}\) .
题目描述说空点不是任何一只动物的领地,其实意思是狼可以通过空点来进攻羊.
所以狼有两种方式进攻羊:
因此该题建图的思路就出来了.
源点和汇点怎么处理呢?
枚举第 \(i\) 只狼,从源点 \(s\) 向它连一条容量为无限的边.
枚举第 \(i\) 只狼,从它向汇点 \(t\) 连一条容量为无限的边.
你不可能将任何一只狼或者任何一只羊莫名删掉,因此容量为无限.
跑一便最小割即可.
SF("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
SF("%d", &x);
num[i][j] = ++sum;
if(x == 1) id1[++len1].first = i, id1[len1].second = j;
else if(x == 2) id2[++len2].first = i, id2[len2].second = j;
else id3[++len3].first = i, id3[len3].second = j;
}
}
int S = 0, T = sum + 1;
for(int i = 1; i <= len1; i++) add(S, num[id1[i].first][id1[i].second], 0x3f3f3f3f), add(num[id1[i].first][id1[i].second], S, 0);
for(int i = 1; i <= len2; i++) add(num[id2[i].first][id2[i].second], T, 0x3f3f3f3f), add(T, num[id2[i].first][id2[i].second], 0);
for(int i = 1; i <= len1; i++) {
for(int j = 1; j <= len3; j++) {
if(abs(id1[i].first - id3[j].first) + abs(id1[i].second - id3[j].second) == 1) add(num[id1[i].first][id1[i].second], num[id3[j].first][id3[j].second], 1), add(num[id3[j].first][id3[j].second], num[id1[i].first][id1[i].second], 0);
}
}
for(int i = 1; i <= len3; i++) {
for(int j = 1; j <= len2; j++) {
if(abs(id3[i].first - id2[j].first) + abs(id3[i].second - id2[j].second) == 1) add(num[id3[i].first][id3[i].second], num[id2[j].first][id2[j].second], 1), add(num[id2[j].first][id2[j].second], num[id3[i].first][id3[i].second], 0);
}
}
for(int i = 1; i <= len3; i++) {
for(int j = 1; j <= len3; j++) {
if(i == j) continue;
if(abs(id3[i].first - id3[j].first) + abs(id3[i].second - id3[j].second) == 1) add(num[id3[i].first][id3[i].second], num[id3[j].first][id3[j].second], 1), add(num[id3[j].first][id3[j].second], num[id3[i].first][id3[i].second], 0);
}
}
for(int i = 1; i <= len1; i++) {
for(int j = 1; j <= len2; j++) {
if(abs(id1[i].first - id2[j].first) + abs(id1[i].second - id2[j].second) == 1) add(num[id1[i].first][id1[i].second], num[id2[j].first][id2[j].second], 1), add(num[id2[j].first][id2[j].second], num[id1[i].first][id1[i].second], 0);
}
}
传送门 。
Algorithm:费用流 。
初看此题似乎看不出来得用费用流。没关系,我们先站在最大流的角度思考一下问题.
需要我们找到 2 条路线:一条要从 \(s\) 到 \(t\) ,另一条要从 \(t\) 到 \(s\) ,并且往返途中每座城市只能经过一次。不难想到拆点。对于点 \(i\) ,拆成入点 \(in_i\) 和出点 \(out_i\) 。从 \(in_i\) 向 \(out_i\) 连接一条容量为 1 的边,表示该点最多经过一次。特别地, \(in_s\) 和 \(out_s\) 之间的容量为 2, \(in_t\) 和 \(out_t\) 之间的容量也为 2。对于两个点 \(u\) 和 \(v\) ,如果它们之间有路径,则从 \(out_u\) 向 \(in_v\) 连接一条容量为无限的边.
做题经验告诉我们,此题可以转化成从 \(s\) 到 \(t\) 找到 2 条不同的路径,再输出答案即可.
当然,如果最大流不为 2,说明 \(s\) 和 \(t\) 不连通,输出无解.
至此,本题结束。了吗?
事实告诉我们,如果单单只跑最大流并判断无解,只能拿到 \(27pts\) ,为什么会错呢?
因为我们要保证路过的城市尽可能多,而不是仅仅找出 2 条路径.
这就是此题需要费用流的原因.
对于每一个点 \(i\) ,在 \(in_i\) 和 \(out_i\) 之间的边上加上 1 点费用,表示流经了一座城市。其它的所有边费用均为 0,再跑一遍最大费用最大流就解决了此题.
补:将所有城市的名字用 \(map\) 映射成数字后比较好处理.
S = 0, T = 2 * n + 1;
for(int i = 1; i <= n; i++) {
cin >> u;
mp[u] = ++_, Mp[_] = u; //map映射
if(i == 1) add(S, mp[u], 2, 0), add(mp[u], S, 0, 0), add(mp[u], mp[u] + n, 2, -1), add(mp[u] + n, mp[u], 0, 1);
else if(i == n) add(mp[u], T, 2, 0), add(T, mp[u], 0, 0), add(mp[u], mp[u] + n, 2, -1), add(mp[u] + n, mp[u], 0, 1);
else add(mp[u], mp[u] + n, 1, -1), add(mp[u] + n, mp[u], 0, 1);
} //将每个费用取反后跑最小费用,跑出来的答案取反就是最大费用了
for(int i = 1; i <= m; i++) {
cin >> u >> v;
add(mp[u] + n, mp[v], 0x3f3f3f3f, 0), add(mp[v], mp[u] + n, 0, 0);
}
给一下我习惯用的拉答案的方式供参考:
void get_res(int x) {
if(x == T) return;
res[len][++res[len][0]] = (x > n ? x - n : x);
for(int i = head[x]; i; i = edge[i].next) {
int to = edge[i].to;
if(i & 1) continue; //链式前向星的性质
if(edge[i ^ 1].c) {
edge[i ^ 1].c--;
get_res(to);
break;
}
}
}
-----------------------------------------分割线-------------------------------------------
for(int i = head[S]; i; i = edge[i].next) {
if(i & 1) continue;
while(edge[i ^ 1].c) {
edge[i ^ 1].c--;
len++;
get_res(edge[i].to);
}
}
int len1 = unique(res[0] + 1, res[0] + 1 + res[0][0]) - res[0] - 1;
int len2 = unique(res[1] + 1, res[1] + 1 + res[1][0]) - res[1] - 1;
cout << len1 + len2 - 2 << endl;
for(int i = 1; i < len1; i++) cout << Mp[res[0][i]] << endl;
for(int i = len2; i; i--) cout << Mp[res[1][i]] << endl;
这种方式每次只能拉 1 点流量,较为耗时,但已经足以面对绝大多数情况了.
传送门 。
Algorithm:上下界网络流 。
通过读题,不难发现每条边都至少要经过一次来打扫雪道,因此每条边的容量的下界为 1,上界为无限,跑一遍无源汇上下界最小流即可.
具体地说,先建立超级源点 \(s\) 和超级汇点 \(t\) , \(s\) 连向所有入度为 0 的点,下界为 0,上界为无限;所以出度为 0 的点连向 \(t\) ,下界为 0,上界为无限。跑一遍有源汇上下界最小流即答案.
不放了,见上面的模板,改动不大.
完结撒花~~~ 。
最后此篇关于【网络流】总结的文章就讲到这里了,如果你想了解更多关于【网络流】总结的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
这个问题在这里已经有了答案: Why filter() after flatMap() is "not completely" lazy in Java streams? (8 个答案) 关闭 6
我正在创建一个应用程序来从 Instagram 收集数据。我正在寻找像 Twitter 流 API 这样的流 API,这样我就可以自动实时收集数据而无需发送请求。 Instagram 有类似的 API
我正在使用 Apache Commons 在 Google App Engine 中上传一个 .docx 文件,如此链接中所述 File upload servlet .上传时,我还想使用 Apach
我尝试使用 DynamoDB 流和 AWS 提供的 Java DynamoDB 流 Kinesis 适配器捕获 DynamoDB 表更改。我正在 Scala 应用程序中使用 AWS Java 开发工具
我目前有一个采用 H.264 编码的 IP 摄像机流式视频 (RTSP)。 我想使用 FFmpeg 将此 H.264 编码流转换为另一个 RTSP 流,但 MPEG-2 编码。我该怎么做?我应该使用哪
Redis 流是否受益于集群模式?假设您有 10 个流,它们是分布在整个集群中还是都分布在同一节点上?我计划使用 Redis 流来实现真正的高吞吐量(200 万条消息/秒),所以我担心这种规模的 Re
这件事困扰了我一段时间。 所以我有一个 Product 类,它有一个 Image 列表(该列表可能为空)。 我想做 product.getImages().stream().filter(...) 但
是否可以使用 具有持久存储的 Redis 流 还是流仅限于内存数据? 我知道可以将 Redis 与核心数据结构的持久存储一起使用,但我已经能够理解是否也可以使用 Redis 中的流的持久存储。 最佳答
我开始学习 Elixir 并遇到了一个我无法轻松解决的挑战。 我正在尝试创建一个函数,该函数接受一个 Enumerable.t 并返回另一个 Enumerable.t ,其中包含下 n 个项目。它与
我试图从 readLine 调用创建一个无限的字符串流: import java.io.{BufferedReader, InputStreamReader} val in = new Buffere
你能帮我使用 Java 8 流 API 编写以下代码吗? SuperUser superUser = db.getSuperUser; for (final Client client : super
我正在尝试服用补品routeguide tutorial,并将客户端变成rocket服务器。我只是接受响应并将gRPC转换为字符串。 service RouteGuide { rpc GetF
流程代码可以是run here. 使用 flow,我有一个函数,它接受一个键值对对象并获取它的值 - 它获取的值应该是字符串、数字或 bool 值。 type ValueType = string
如果我有一个函数返回一个包含数据库信息的对象或一个空对象,如下所示: getThingFromDB: async function(id:string):Promise{ const from
我正在尝试使用javascript api和FB.ui将ogg音频文件发布到流中, 但是我不知道该怎么做。 这是我给FB.ui的电话: FB.ui( { method: '
我正在尝试删除工作区(或克隆它以使其看起来像父工作区,但我似乎两者都做不到)。但是,当我尝试时,我收到此消息:无法删除工作区 test_workspace,因为它有一个非空的默认组。 据我所知,这意味
可以使用 Stream|Map 来完成此操作,这样我就不需要将结果放入外部 HashMap 中,而是使用 .collect(Collectors.toMap(...)); 收集结果? Map rep
当我们从集合列表中获取 Stream 时,幕后到底发生了什么?我发现很多博客都说Stream不存储任何数据。如果这是真的,请考虑代码片段: List list = new ArrayList(); l
我对流及其工作方式不熟悉,我正在尝试获取列表中添加的特定对象的出现次数。 我找到了一种使用Collections来做到这一点的方法。其过程如下: for (int i = 0; i p.conten
我希望将一个 map 列表转换为另一个分组的 map 列表。 所以我有以下 map 列表 - List [{ "accId":"1", "accName":"TestAcc1", "accNumber
我是一名优秀的程序员,十分优秀!