「网络流 24 题」小结

前言:

  前阵子为了在刷「网络流 24 题」,于是就有了这篇小节。但因为很多题目模型相似,所以只在下面的表格里大致列一下,只有加粗的题目有详细的题解。

题目名称: 模型:
搭配飞行员 二分图最大匹配
太空飞行计划 最小割(最大权闭合子图)
最小路径覆盖 最小路径覆盖
魔术球 最小路径覆盖,增量增广
圆桌聚餐 最大流
最长递增子序列 最大流
试题库 最大流
方格取数 最小割
餐巾计划 最小费用最大流
软件补丁 最短路
数字梯形 最大费用最大流
运输问题 最小费用最大流
分配问题 最大费用最大流
负载平衡 最小费用最大流
最长 k 可重区间集 最大费用最大流

loj_6001 太空飞行计划

题目:

  W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 ,和进行这些实验需要使用的全部仪器的集合 。实验 需要用到的仪器是 的子集
  配置仪器 的费用为 美元。实验 的赞助商已同意为该实验结果支付 美元。W 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
  对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。

思路:

  因为权值有正有负不好直接考虑,所以先假设已经得到了所有实验的赞助,然后再决策是购买实验所需的仪器,还是放弃实验退还赞助。
  在实验与源点之间流一条权值为赞助的边,仪器与汇点之间连一条权值为仪器费用的边。再用权值为 的边连接实验与仪器,这样的图中的最小割就是要放弃的最小价值。
  ps:写完之后有人说这就是 最大权闭合子图 的模板,不过能自己推出来总是好一点的嘛.....

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 105;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {mset(HEAD, 0); tot = 0;}
    void add(int x, T w) { NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w; }
    T& operator[] (int x) { return W[x]; }
};
struct Edge {
    int flow, to;
};
Link<N, N * N, Edge> G;

inline int rev(int x) {
    return ((x - 1) ^ 1) + 1;
}
void addEdge(int u, int v, int d) {
    G.add(u, (Edge) {d, v});
    G.add(v, (Edge) {0, u});
}

int que[N], mark[N];
bool bfs(int s, int t) {
    mset(mark, 0);
    int hed = 1, tai = 0;
    que[++tai] = s; mark[s] = 1;
    while(hed <= tai) {
        int o = que[hed++];
        erep(k, G, o) {
            Edge e = G[k];
            if(e.flow == 0) continue;
            if(mark[e.to]) continue;
            mark[e.to] = mark[o] + 1;
            que[++tai] = e.to;
        }
    }
    return mark[t];
}
int dfs(int o, int mn, int t) {
    if(o == t) return mn;
    int ans = 0;
    erep(k, G, o) {
        Edge e = G[k];
        if(e.flow == 0) continue;
        if(mark[e.to] - mark[o] != 1) continue;
        int tmp = dfs(e.to, min(mn, e.flow), t);
        G[k].flow -= tmp; mn -= tmp;
        G[rev(k)].flow += tmp; ans += tmp;
        if(mn == 0) break;
    }
    return ans;
}

int dinic(int s, int t) {
    int ans = 0;
    while(bfs(s, t)) ans += dfs(s, 1e9, t);
    return ans;
}

vector<int> vec[N], ans1, ans2;

int main() {
    // freopen("data.in", "r", stdin);
    int n, m, a, s, t;
    char c;
    scanf("%d%d", &m, &n);
    s = n + m + 1; t = n + m + 2;
    int ans = 0;
    rep(i, 1, m) {
        scanf("%d", &a);
        ans += a;
        addEdge(i, t, a);
        do {
            scanf("%d%c", &a, &c);
            vec[i].push_back(a);
            addEdge(a + m, i, 1e9);
        } while(c != '\n' && c != '\\r');
    }
    rep(i, 1, n) {
        scanf("%d", &a);
        addEdge(s, i + m, a);
    }
    ans -= dinic(s, t);
    rep(i, 1, m) if(!mark[i]) ans1.push_back(i);
    rep(i, 1, n) if(!mark[i + m]) ans2.push_back(i);
    for(int x : ans1) printf("%d%c", x, " \n"[x == ans1.back()]);
    for(int x : ans2) printf("%d%c", x, " \n"[x == ans2.back()]);
    printf("%d\n", ans);
    return 0;
}

loj_6005 最长递增子序列

题目:

  给定正整数序列 ,以下递增子序列均为非严格递增。
  1.计算其最长递增子序列的长度
  2.计算从给定的序列中最多可取出多少个长度为 的递增子序列。
  3.如果允许在取出的序列中多次使用 ,则从给定序列中最多可取出多少个长度为 的递增子序列。

思路:

  首先问题1可以直接 dp 得到答案,然后再考虑求递增子序列的个数。为了保证得到的子序列长度为 ,只有当 能由 转移得到时,才在 之间连边。为保证每个数字只取一次,再把每个数字拆成两个点,连一条流量为 的边即可。问题 3 就只要把 的限制去掉即可(加一条权值为 的边即可)。

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 1005, M = N * N;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {mset(HEAD, 0); tot = 0;}
    void add(int x, T w) { NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w; }
    T& operator[] (int x) { return W[x]; }
};
struct Edge {
    int to, flow;
};
Link<N, M * 2, Edge> G;
int rev(int k) {
    return ((k - 1) ^ 1) + 1;
}
void addEdge(int u, int v, int d) {
    G.add(u, (Edge) {v, d});
    G.add(v, (Edge) {u, 0});
}

int que[N], mark[N];
bool bfs(int s, int t) {
    mset(mark, 0);
    int hed = 1, tai = 0;
    que[++tai] = s; mark[s] = 1;
    while(hed <= tai) {
        int o = que[hed++];
        erep(k, G, o) {
            Edge e = G[k];
            if(e.flow && !mark[e.to]) {
                mark[e.to] = mark[o] + 1;
                que[++tai] = e.to;
            }
        }
    }
    return mark[t];
}
int dfs(int o, int mn, int t) {
    if(o == t) return mn;
    int ans = 0;
    erep(k, G, o) {
        Edge e = G[k];
        if(!e.flow || mark[e.to] - mark[o] != 1) continue;
        int tmp = dfs(e.to, min(mn, e.flow), t);
        mn -= tmp; G[k].flow -= tmp;
        ans += tmp; G[rev(k)].flow += tmp;
        if(mn == 0) break;
    }
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    while(bfs(s, t)) {
        int tmp = ans;
        ans += dfs(s, 1e9, t);
        assert(ans != tmp);
    }
    return ans;
}

int a[N], dp[N];

int main() {
    // freopen("data.in", "r", stdin);
    int n;
    scanf("%d", &n);
    rep(i, 1, n) scanf("%d", a + i);
    rep(i, 1, n) 
        rep(j, 0, i - 1) 
            if(a[i] >= a[j]) 
                tomax(dp[i], dp[j] + 1);
    int mx = 0;
    rep(i, 1, n) tomax(mx, dp[i]);
    printf("%d\n", mx);
    rep(i, 1, n) addEdge(i, i + n, 1);
    int s = 2 * n + 1, t = 2 * n + 2;
    rep(i, 1, n) {
        if(dp[i] == 1) addEdge(s, i, 1e9);
        if(dp[i] == mx) addEdge(i + n, t, 1e9);
        rep(j, 1, i - 1) {
            if(a[i] >= a[j] && dp[i] == dp[j] + 1)
                addEdge(j + n, i, 1);
        }
    }
    int ans = dinic(s, t);
    printf("%d\n", ans);
    addEdge(1, 1 + n, 1e9);
    addEdge(n, n + n, 1e9);
    int tmp = dinic(s, t);
    if(tmp < n) ans += tmp;
    printf("%d\n", ans);
    return 0;
}

loj_6008 餐巾计划

题目:

  一个餐厅在相继的 天里,每天需用的餐巾数不尽相同。假设第 天需要 块餐巾。餐厅可以购买新的餐巾,每块餐巾的费用为 分;或者把旧餐巾送到快洗部,洗一块需 天,其费用为 分;或者送到慢洗部,洗一块需 天,其费用为 分($$ S < F $$)。   每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。   试设计一个算法为餐厅合理地安排好 $$ n $$ 天中餐巾使用计划,使总的花费最小。

思路:

  一开始对洗餐巾的想法一直是:每次洗餐巾时就把流量引到以后的日子去使用,从源点流出的流量认为是新买的。但这样流到汇点的流量就不能满足要求了。
  那就不要把脏的餐巾与干净的餐巾挂钩,可以认为每天可以得到 条脏餐巾,而那些用完的餐巾就直接流到汇点去。这样连边就会比较清晰了。(用 表示源汇点, 表示第 天的脏餐巾和餐巾)
   表示第 天得到的脏餐巾。
   表示第 天用掉的餐巾。
   表示第 天买的新餐巾。
   表示第 天从到快洗部的脏餐巾。
   表示第 天从到慢洗部的脏餐巾。
   表示第 天延期到送洗的餐巾。
  这样就表达出了所有的操作,求最小费用最大流即可。

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 2005, M = 12005;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {mset(HEAD, 0); tot = 0;}
    void add(int x, T w) { NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w; }
    T& operator[] (int x) { return W[x]; }
};

struct Edge {
    int to, flow, cost;
};

Link<N, M * 2, Edge> G;
void addEdge(int u, int v, int d, int c) {
    G.add(u, (Edge) {v, d, c});
    G.add(v, (Edge) {u, 0, -c});
}
inline int rev(int k) {
    return ((k - 1) ^ 1) + 1;
}

struct Queue {
    int hed, tai, q[N];
    bool empty() {return hed == tai;}
    void clear() {hed = tai = 0;}
    int pop() {int a = q[hed]; hed = (hed + 1) % N; return a;}
    void push(int a) {q[tai] = a; tai = (tai + 1) % N;}
} que;
int dis[N];
bool inq[N];
int spfa(int s, int t) {
    mset(dis, 63); dis[s] = 0;
    mset(inq, 0); que.clear();
    que.push(s); inq[s] = true;
    while(!que.empty()) {
        int o = que.pop(); inq[o] = false;
        erep(k, G, o) {
            Edge e = G[k];
            if(e.flow == 0) continue;
            if(tomin(dis[e.to], dis[o] + e.cost) && !inq[e.to]) {
                que.push(e.to); inq[e.to] = true;
            }
        }
    }
    return dis[t];
}

bool mark[N];
int dfs(int o, int mn, int t) {
    mark[o] = true;
    if(o == t) return mn;
    int ans = 0;
    erep(k, G, o) {
        Edge e = G[k];
        if(e.flow == 0 || mark[e.to] || dis[e.to] != dis[o] + e.cost) continue;
        int tmp = dfs(e.to, min(mn, e.flow), t);
        G[k].flow -= tmp; mn -= tmp;
        G[rev(k)].flow += tmp; ans += tmp;
        if(!mn) break;
    }
    return ans;
}

int mcmf(int s, int t) {
    int d, c, ans = 0;
    while((c = spfa(s, t)) <= 1e9) {
        do {
            mset(mark, 0);
            ans += c * dfs(s, 1e9, t);
        } while(mark[t]);
    }
    return ans;
}

int main() {
    int n, p, a, f, b, e, x;
    scanf("%d%d%d%d%d%d", &n, &p, &a, &f, &b, &e);
    int s = 2 * n + 1, t = s + 1;
    rep(i, 1, n) {
        scanf("%d", &x);
        addEdge(s, i, x, 0);
        addEdge(i + n, t, x, 0);
        addEdge(s, i + n, 1e9, p);
    }
    rep(i, 1, n - 1) addEdge(i, i + 1, 1e9, 0);
    rep(i, 1, n - a) addEdge(i, i + a + n, 1e9, f);
    rep(i, 1, n - b) addEdge(i, i + b + n, 1e9, e);
    printf("%d\n", mcmf(s, t));
    return 0;
}

loj_6014 最长 k 可重区间集

题目:

   给定实直线 个开区间组成的集合 ,和一个正整数 ,试设计一个算法,从开区间集合 中选取出开区间集合 ,使得在实直线 的任何一点 中包含点 的开区间个数不超过 。且 达到最大。这样的集合 称为开区间集合 的最长 可重区间集。 称为最长 可重区间集的长度。
   对于给定的开区间集合 和正整数 ,计算开区间集合 的最长 可重区间集的长度。

思路:

   emmm一开始的想法是用离散 弄出一个一个单位块,然后限制经过每个单位块的流量,但是发现这样不能保证取出的区间是集合中的区间。
   于是就换个角度出发,如果要选中 这个区间,那么从 开始当前选择的区间个数就要减 ,到了 是可选择的个数又能加 。所以可以用流量表示当前能选择的区间个数,对每个区间连一条 的边,表示选择这个区间。对每个点连一条 表示什么都不做。然后求最大费用最大流即可。

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 1005, M = N * 4;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {mset(HEAD, 0); tot = 0;}
    void add(int x, T w) { NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w; }
    T& operator[] (int x) { return W[x]; }
};

struct Edge {
    int to, flow, cost;
};
Link<N, M, Edge> G;
inline int rev(int k) {
    return ((k - 1) ^ 1) + 1;
}
void addEdge(int u, int v, int cost, int flow) {
    G.add(u, (Edge) {v, flow, cost});
    G.add(v, (Edge) {u, 0, -cost});
}

struct Queue {
    int q[N], hed, tai;
    bool empty() {return hed == tai;}
    int pop() {int a = q[hed++]; if(hed == N) hed = 0; return a;}
    void push(int a) {q[tai++] = a; if(tai == N) tai = 0;}
} que;

int dis[N];
bool inq[N];
int spfa(int s, int t) {
    mset(dis, 0x8f); dis[s] = 0;
    que.push(s); inq[s] = true;
    while(!que.empty()) {
        int o = que.pop(); inq[o] = false;
        erep(k, G, o) {
            Edge e = G[k];
            if(e.flow == 0) continue;
            if(tomax(dis[e.to], dis[o] + e.cost) && !inq[e.to]) {
                inq[e.to] = true; que.push(e.to);
            }
        }
    }
    return dis[t];
}
bool vis[N];
int dfs(int o, int mn, int t) {
    vis[o] = true;
    if(o == t) return mn;
    int ans = 0;
    erep(k, G, o) {
        Edge e = G[k];
        if(e.flow == 0 || vis[e.to] || dis[e.to] != dis[o] + e.cost) continue;
        int tmp = dfs(e.to, min(mn, e.flow), t);
        G[k].flow -= tmp; mn -= tmp;
        G[rev(k)].flow += tmp; ans += tmp;
        if(mn == 0) break;
    }
    return ans;
}
int mcmf(int s, int t) {
    int c, d, ans = 0;
    while((c = spfa(s, t)) > 0) {
        do {
            mset(vis, 0);
            d = dfs(s, 1e9, t);
            ans += c * d;
        } while(vis[t]);
    }
    return ans;
}

int l[N], r[N], vec[N * 2];
int main() {
    // freopen("data.in", "r", stdin);
    int n, k, tot = 0;
    scanf("%d%d", &n, &k);
    rep(i, 1, n) {
        scanf("%d%d", &l[i], &r[i]);
        if(l[i] > r[i]) swap(l[i], r[i]);
        vec[++tot] = l[i];
        vec[++tot] = r[i];
    }
    sort(vec + 1, vec + 1 + tot);
    tot = unique(vec + 1, vec + 1 + tot) - vec - 1;
    int s = tot + 1, t = s + 1;
    addEdge(s, 1, 0, k); addEdge(tot, t, 0, k);
    rep(i, 1, tot - 1) addEdge(i, i + 1, 0, 1e9);
    rep(i, 1, n) {
        int a = lower_bound(vec + 1, vec + 1 + tot, l[i]) - vec;
        int b = lower_bound(vec + 1, vec + 1 + tot, r[i]) - vec;
        addEdge(a, b, r[i] - l[i], 1);
    }
    printf("%d\n", mcmf(s, t));
    return 0;
}