上下界网络流、最小费用最大流
前言
（点了首这么悲伤的BGM，见谅）
回到学校就把系统玩崩了（挂滚有线网卡了），于是从Manjaro跳到Ubuntu T^T
然后又被催更了 T^T
- 综合：
http://acm.pku.edu.cn/summerschool/gw_netflow.pdf - 有上下界的网络流
https://blog.csdn.net/YxuanwKeith/article/details/52238928
https://www.cnblogs.com/kane0526/archive/2013/04/05/3001108.html
https://www.cnblogs.com/liu-runda/p/6262832.html
https://blog.csdn.net/Hanks_o/article/details/77995557
https://blog.csdn.net/blue_cuso4/article/details/78921497
https://dozbear.com/bounded-network-flow-review/index.html - 最小费用最大流
https://riteme.github.io/blog/2016-2-2/mincost-maxflow.html
Reactor Cooling - SGU 194
题意
给定无源汇上下界网络求可行流
思路
模板题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200 + 15;
const int inf = 0x3f3f3f3f;
int pre[N], d[N], cur[N], gap[N];
int cap[N][N], flow[N][N], lower_flow[N][N];
int u[N*N], v[N*N];
inline void init(){
memset(cap[0], 0, sizeof(cap));
memset(flow[0], 0, sizeof(flow));
}
inline void addEdge(int u, int v, int val){
cap[u][v] += val;
cap[v][u] += val;
flow[v][u] += val;
}
int ISAP(int src, int des, int n){
memset(cur, 0, sizeof(cur));
memset(gap, 0, sizeof(gap));
memset(d, 0, sizeof(d));
int u = pre[src] = src;
int sum = 0;
gap[0] = n;
while(d[src] < n){
if(u == des){
int v, aug = inf;
for(u = pre[des], v = des; v != src; v = u, u = pre[u]) aug = min(aug, cap[u][v] - flow[u][v]);
for(u = pre[des], v = des; v != src; v = u, u = pre[u]){
flow[u][v] += aug;
flow[v][u] -= aug;
}
sum += aug;
continue;
}
bool flag = false;
for(int& v = cur[u]; v < n; v++){
if(u == v) continue;
if(d[u] == d[v] + 1 && cap[u][v] - flow[u][v]){
pre[v] = u;
u = v;
flag = true;
break;
}
}
if(!flag){
int mind = n;
for(int v = 0; v < n; v++){
if(u == v) continue;
if(cap[u][v] - flow[u][v] && d[v] < mind){
mind = d[v];
cur[u] = v;
}
}
if((--gap[d[u]]) == 0) break;
d[u] = mind + 1;
gap[d[u]]++;
u = pre[u];
}
}
return sum;
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
int sum = 0;
for(int i = 1; i <= m; i++){
int l, r;
scanf("%d%d%d%d", &u[i], &v[i], &l, &r);
addEdge(u[i], v[i], r - l);
addEdge(u[i], 0, l); // 0为超级汇点，n+1为超级源点
addEdge(n + 1, v[i], l);
lower_flow[u[i]][v[i]] = l;
sum += l; // 统计下界流
}
if(sum <= ISAP(n + 1, 0, n + 2)){ // 可行流 >= 下界流，则ok
puts("YES");
for(int i = 1; i <= m; i++){
printf("%d\n", flow[u[i]][v[i]] + lower_flow[u[i]][v[i]]); //边中的流量 + 下界的流量
}
}else{
puts("NO");
}
}
}
Shoot the Bullet - ZOJ 3229
题意
本题题意改自网络
一个人给m个女神拍照，计划拍照n天，每一天屌丝给给定的C个女神拍照，每天拍照数不能超过D张，而且给每个女神i拍照有数量限制[Li，Ri]，对于每个女神n天的拍照总和不能少于Gi，如果有解求最多能拍多少张照，并求每天给对应女神拍多少张照；否则输出-1
思路
首先是建图，设一源点s和汇点t，引入m个节点代表每个女神，从这m个节点各自引出一条[Gi, inf]边连接，再加入n个节点表示每一天，从s到每一天的节点各连接一条[0, D]的边，最后连接m个女神节点和n个天的节点之间[Li, Ri]的边，再引入超级源点和超级汇点作等价转化
从t到s连接一条inf的边从ss到tt跑最大流，再从s到t跑一遍最大流，即得到最终的最大流
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1500 + 15;
const int M = 1e6 + 15;
const int inf = 0x3f3f3f3f;
struct edge{
int v, val, cap, next;
edge(int pv, int pval, int pcap, int pnext): v(pv), val(pval), cap(pcap), next(pnext) {}
edge() {}
};
edge e[M];
int tot, head[N], pre[N], d[N], cur[N], gap[N];
int anse[M], pans;
inline void init(){
memset(head, -1, sizeof(head));
tot = 0, pans = 0;
}
inline void addEdge(int u, int v, int val){
e[tot] = edge(v, 0, val, head[u]);
head[u] = tot++;
e[tot] = edge(u, val, val, head[v]);
head[v] = tot++;
}
int ISAP(int src, int des, int n){
memcpy(cur, head, sizeof(head));
memset(gap, 0, sizeof(gap));
memset(d, 0, sizeof(d));
int u = pre[src] = src;
int sum = 0;
gap[0] = n;
while(d[src] < n){
if(u == des){
int v, aug = inf;
for(u = pre[des], v = des; v != src; v = u, u = pre[u]) aug = min(aug, e[cur[u]].cap - e[cur[u]].val);
for(u = pre[des], v = des; v != src; v = u, u = pre[u]){
e[cur[u]].val += aug;
e[cur[u]^1].val -= aug;
}
sum += aug;
continue;
}
bool flag = false;
for(int& i = cur[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[u] == d[v] + 1 && e[i].cap - e[i].val){
pre[v] = u;
u = v;
flag = true;
break;
}
}
if(!flag){
int mind = n;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(e[i].cap - e[i].val && d[v] < mind){
mind = d[v];
cur[u] = i;
}
}
if((--gap[d[u]]) == 0) break;
d[u] = mind + 1;
gap[d[u]]++;
u = pre[u];
}
}
return sum;
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
int tt = n + m + 2, ss = n + m + 3;
int s = 0, t = n + m + 1;
int sum = 0;
for(int i = 1; i <= m; i++){
int val;
scanf("%d", &val);
addEdge(n + i, tt, val);
addEdge(ss, t, val);
addEdge(n + i, t, inf);
sum += val;
}
for(int i = 1; i <= n; i++){
int k, val;
scanf("%d%d", &k, &val);
addEdge(s, i, val);
while(k--){
int idx, l, r;
scanf("%d%d%d", &idx, &l, &r);
addEdge(i, tt, l);
anse[pans++] = tot - 2;
addEdge(ss, n + 1 + idx, l);
addEdge(i, n + 1 + idx, r - l);
anse[pans++] = tot - 2;
sum += l;
}
}
addEdge(t, s, inf);
int ans = ISAP(ss, tt, n + m + 4);
if(sum <= ans){
//不用 += 是因为上一次的结果贮存在t到s这条边中，再跑一次最大流会利用这个结果
ans = ISAP(s, t, n + m + 4);
printf("%d\n", ans);
for(int i = 0; i < pans; i += 2){
printf("%d\n", e[anse[i]].val + e[anse[i + 1]].val);
}
}else{
puts("-1");
}
puts("");
}
}
Flow construction - SGU 176
题意
给定网络，输入中每条边的最后一个数若为0，则表示为[0, val]，若为1，则表示为[val, val]，求该网络从1到N的最小流
思路
模板题
进行等价转换后，先跑一遍ss到tt的最大流，连上t到s的inf边，再跑一遍ss到tt的最大流，最终t->s边中的流量即是答案
（具体原因个人不是很懂，望有dalao能指点指点）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e2 + 15;
const int M = 1e5 + 15;
const int inf = 0x3f3f3f3f;
struct edge{
int v, val, cap, next;
edge(int pv, int pval, int pcap, int pnext): v(pv), val(pval), cap(pcap), next(pnext) {}
edge() {}
};
edge e[M << 1];
int tot, head[N], pre[N], d[N], cur[N], gap[N];
int anse[M << 1], pans;
inline void init(){
memset(head, -1, sizeof(head));
tot = 0, pans = 0;
}
inline void addEdge(int u, int v, int val){
e[tot] = edge(v, 0, val, head[u]);
head[u] = tot++;
e[tot] = edge(u, val, val, head[v]);
head[v] = tot++;
}
int ISAP(int src, int des, int n){
memcpy(cur, head, sizeof(head));
memset(gap, 0, sizeof(gap));
memset(d, 0, sizeof(d));
int u = pre[src] = src;
int sum = 0;
gap[0] = n;
while(d[src] < n){
if(u == des){
int v, aug = inf;
for(u = pre[des], v = des; v != src; v = u, u = pre[u]) aug = min(aug, e[cur[u]].cap - e[cur[u]].val);
for(u = pre[des], v = des; v != src; v = u, u = pre[u]){
e[cur[u]].val += aug;
e[cur[u]^1].val -= aug;
}
sum += aug;
continue;
}
bool flag = false;
for(int& i = cur[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[u] == d[v] + 1 && e[i].cap - e[i].val){
pre[v] = u;
u = v;
flag = true;
break;
}
}
if(!flag){
int mind = n;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(e[i].cap - e[i].val && d[v] < mind){
mind = d[v];
cur[u] = i;
}
}
if((--gap[d[u]]) == 0) break;
d[u] = mind + 1;
gap[d[u]]++;
u = pre[u];
}
}
return sum;
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
int s = 1, t = n, ss = 0, tt = n + 1;
int sum = 0;
while(m--){
int u, v, val, type;
scanf("%d%d%d%d", &u, &v, &val, &type);
if(type){
addEdge(u, tt, val);
addEdge(ss, v, val);
sum += val;
}else{
addEdge(u, v, val);
}
anse[pans++] = tot - 2;
}
bool flag = true;
ISAP(ss, tt, n + 2);
addEdge(t, s, inf);
ISAP(ss, tt, n + 2);
for(int i = head[ss]; ~i; i = e[i].next){
if(e[i].cap - e[i].val){
flag = false;
break;
}
}
if(flag){
printf("%d\n", e[tot - 2].val);
for(int i = 0; i < pans; i++){
printf("%d", e[anse[i]].val);
if(i < pans - 1) putchar(' ');
}
puts("");
}else{
puts("Impossible");
}
}
}
Farm Tour - POJ 2135
题意
在给定无向图中，求出从1到N，再从N到1，且不走重复路径的最短路径
思路
最小费用最大流模板题
设边的费用为距离，流量为1，引入超级源点ss连向1，超级汇点tt，n连向tt，流量均为2，费用均为0，跑一遍最大流即可
本题个人觉得非常巧妙地运用了最大流来避免走重复路径
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e3 + 15;
const int M = 1e4 + 15;
const int inf = 0x3f3f3f3f;
struct edge{
int v, val, cost, next;
edge(int pv, int pval, int pcost, int pnext): v(pv), val(pval), cost(pcost), next(pnext) {}
edge() {}
};
edge e[M << 2];
int tot, head[N], pre[N], d[N], cur[N];
bool inq[N];
queue<int> que;
inline void init(){
memset(head, -1, sizeof(head));
tot = 0;
}
inline void addEdge(int u, int v, int val, int cost){
e[tot] = edge(v, val, cost, head[u]);
head[u] = tot++;
e[tot] = edge(u, 0, -cost, head[v]);
head[v] = tot++;
}
bool spfa(int src, int des){
memset(d, 0x3f, sizeof(d));
memset(inq, false, sizeof(inq));
d[src] = 0, pre[src] = src;
que.push(src);
inq[src] = true;
while(!que.empty()){
int u = que.front();
que.pop();
inq[u] = false;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[v] > d[u] + e[i].cost && e[i].val){
d[v] = d[u] + e[i].cost;
pre[v] = u;
cur[v] = i;
if(!inq[v]){
que.push(v);
inq[v] = true;
}
}
}
}
return d[des] != inf;
}
int solve(int src, int des){
int ans = 0;
while(spfa(src, des)){
int aug = inf;
for(int v = des; v != src; v = pre[v]) aug = min(aug, e[cur[v]].val);
for(int v = des; v != src; v = pre[v]){
e[cur[v]].val -= aug;
e[cur[v]^1].val += aug;
}
ans += d[des] * aug;
}
return ans;
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
int ss = 0, tt = n + 1, s = 1, t = n;
while(m--){
int u, v, cost;
scanf("%d%d%d", &u, &v, &cost);
addEdge(u, v, 1, cost);
addEdge(v, u, 1, cost);
}
addEdge(ss, s, 2, 0);
addEdge(t, tt, 2, 0);
printf("%d\n", solve(ss, tt));
}
return 0;
}
