网络流24题

飞行员配对方案问题

题目描述

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入格式

第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总数(n<100)；m 是外籍飞行员数(m<=n)。外籍飞行员编号为 1~m；英国飞行员编号为 m+1~n。

接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。最后以 2个-1 结束。

输出格式

第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。接下来 M 行是最佳飞行员配对方案。每行有 2个正整数 i 和 j，表示在最佳飞行员配对方案中，飞行员 i 和飞行员 j 配对。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。

输入样例

输出样例

二分图最大匹配

#include <bits/stdc++.h>

using namespace std;
const int maxn=30000;
struct node{
    int v,next;
}e[maxn];
int match[maxn],dismatch[maxn],vis[maxn],t,head[maxn],ans,m,n,u,v;
void add(int u,int v){
    t++;
    e[t].v=v;
    e[t].next=head[u];
    head[u]=t;
}
bool dfs(int u) {
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (!vis[v]) {
            vis[v] = 1;
            if (!match[v] || dfs(match[v])) {
                match[v] = u;
                dismatch[u]=v;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    while (scanf("%d%d",&u,&v)){
        if (u==-1&&v==-1){
            break;
        }
        add(u,v);
    }
    for (int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if (dfs(i)){
            ans++;
        }
    }
    if (ans){
        printf("%d
",ans);
        for (int i=1;i<=m;i++){
            if (dismatch[i]){
                printf("%d %d
",i,dismatch[i]);
            }
        }
    }else{
        printf("No Solution!
");
    }
}

网络流建图

超级源点S与1~m连流量为1的边，m+1~n与超级汇点T连流量为1的边，所给的边，连流量为0x3f3f3f3f

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+7;
const int maxm=1e5+7;
const int inf=0x3f3f3f3f;

int n,m,u,v;
struct Dinic {
    struct Edge {
        int next, f, to;
    } e[maxm];
    int head[maxn], dep[maxn], tol, ans;
    int cur[maxn];
    int src, sink, n;

    void add(int u, int v, int f) {
        tol++;
        e[tol].to = v;
        e[tol].next = head[u];
        e[tol].f = f;
        head[u] = tol;
        tol++;
        e[tol].to = u;
        e[tol].next = head[v];
        e[tol].f = 0;
        head[v] = tol;
    }

    bool bfs() {
        queue<int> q;
        memset(dep, -1, sizeof(dep));
        q.push(src);
        dep[src] = 0;
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int i = head[now]; i; i = e[i].next) {
                if (dep[e[i].to] == -1 && e[i].f) {
                    dep[e[i].to] = dep[now] + 1;
                    if (e[i].to == sink)
                        return true;
                    q.push(e[i].to);
                }
            }
        }
        return false;
    }

    int dfs(int x, int maxx) {
        if (x == sink)
            return maxx;
        for (int &i = cur[x]; i; i = e[i].next) {
            if (dep[e[i].to] == dep[x] + 1 && e[i].f > 0) {
                int flow = dfs(e[i].to, min(maxx, e[i].f));
                if (flow) {
                    e[i].f -= flow;
                    e[i ^ 1].f += flow;
                    return flow;
                }
            }
        }
        return 0;
    }

    int dinic(int s, int t) {
        ans = 0;
        this->src = s;
        this->sink = t;
        while (bfs()) {
            for (int i = 0; i <= n; i++)
                cur[i] = head[i];
            while (int d = dfs(src, inf))
                ans += d;
        }
        return ans;
    }

    void init(int n) {
        this->n = n;
        memset(head, 0, sizeof(head));
        tol = 1;
    }
} G;

int main(){
    scanf("%d%d",&m,&n);
    G.init(n+1+m);
    while (scanf("%d%d",&u,&v)){
        if (u==-1&&v==-1){
            break;
        }
        G.add(u,v,inf);
    }
    for (int i=1;i<=m;i++){
        G.add(0,i,1);
    }
    for (int i=m+1;i<=m+n;i++){
        G.add(i,n+m+1,1);
    }
    int ans=G.dinic(0,n+m+1);
    if (ans){
        printf("%d
",ans);
    }else{
        printf("No Solution!
");
    }
}

太空飞行计划问题

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

输入格式

第1行有2 个正整数m和n。m是实验数，n是仪器数。接下来的m 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。

输出格式

第1 行是实验编号；第2行是仪器编号；最后一行是净收益。

输入样例

输出样例

1 2
1 2 3
17

最小路径覆盖问题

运输问题

现在一个图已经建好了,问题是求什么?求的是最小运输费用和对大运输费用,所以这道题是一个最小(大)费用最大流,所以s和所有仓库相连,流为ai,费用为0,将t与所有商店相连,流为bj,费用为0,再将仓库和商店相连,流为inf((极大值)费用为c[i][j].
这样以后会发现这个图很标准,最小费用最大流很容易跑,但是最大费用最小流怎么跑?
可以将问题转换一下,应为最大费用的相反数是所有费用中最小的,所以可以将所有的费用去相反数,最后求出最小费用最大流的结果取相反数就可以了

#include <bits/stdc++.h>
using namespace std;
const int maxn=10010;
const int inf=0x3f3f3f3f;
typedef pair<int,int> PI;
int n,m,a[maxn],b[maxn],c[maxn][maxn];
struct MCFC {
    struct edge {
        int to, next, cap, flow, cost;
    } e[maxn];
    int head[maxn], tol;
    int pre[maxn], dis[maxn];
    bool vis[maxn];
    int N;

    void init(int n) {
        N = n;
        tol = 1;
        memset(head, 0, sizeof(head));
    }

    void addedge(int u, int v, int cap, int cost) {
        tol++;
        e[tol].to = v;
        e[tol].cap = cap;
        e[tol].cost = cost;
        e[tol].flow = 0;
        e[tol].next = head[u];
        head[u] = tol;
        tol++;
        e[tol].to = u;
        e[tol].cap = 0;
        e[tol].flow = 0;
        e[tol].cost = -cost;
        e[tol].next = head[v];
        head[v] = tol;
    }

    bool spfa(int s, int t) {
        queue<int> q;
        for (int i = 0; i <= N; i++) {
            dis[i] = inf;
            vis[i] = false;
            pre[i] = -1;
        }
        dis[s] = 0;
        vis[s] = true;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = false;
            for (int i = head[u]; i; i = e[i].next) {
                int v = e[i].to;
                if (e[i].cap > e[i].flow && dis[v] >dis[u] + e[i].cost) {
                    dis[v] = dis[u] + e[i].cost;
                    pre[v] = i;
                    if (!vis[v]) {
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
        }
        if (pre[t] == -1) return false;
        else return true;
    }

    int cost = 0;

    PI mcmf(int s, int t) {
        int flow = 0;
        cost = 0;
        while (spfa(s, t)) {
            int minn = inf;
            for (int i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) {
                if (minn > e[i].cap - e[i].flow) {
                    minn = e[i].cap - e[i].flow;
                }
            }
            for (int i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) {
                e[i].flow += minn;
                e[i ^ 1].flow -= minn;
                cost += e[i].cost * minn;
            }
            flow += minn;
        }
        return make_pair(cost,flow);
    }
} G;

int main(){
    scanf("%d%d",&m,&n);
    G.init(n+m+1);
    for (int i=1;i<=m;i++){
        scanf("%d",&a[i]);
       G.addedge(0,i,a[i],0);
    }
    for (int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        G.addedge(i+m,n+m+1,b[i],0);
    }
    for (int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&c[i][j]);
            G.addedge(i,j+m,inf,c[i][j]);
        }
    }
    printf("%d
",G.mcmf(0,n+m+1).first);
    G.init(n+m+1);
    for (int i=1;i<=m;i++){
        G.addedge(0,i,a[i],0);
    }
    for (int i=1;i<=n;i++){
        G.addedge(i+m,n+m+1,b[i],0);
    }
    for (int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            G.addedge(i,j+m,inf,-c[i][j]);
        }
    }
    printf("%d
",-G.mcmf(0,n+m+1).first);
}

骑士共存问题

很明显能看出来同色的格子之间是不会相互攻击的。

于是我们就可以把这张图分成一张二分图了，然后建边跑最大流。

有攻击关系的点需要连一条流量为1的边。

不过值得注意的是，要优化建边方法，不然会超时。

既然是二分图，我们考虑黄色格子代表的点与S连边，红色格子代表的点与T连边，在考虑攻击关系的时候，只从黄色格子连向红色格子就可以了（因为互相攻击，所以是等价的，当然与上述方案完全反过来建边也可以）。

我们要求的是最多的共存骑士，所以是明显的二分图最大独立集的问题，求出的最大流相当于一个最小割，用总数n*n-m再减去这个最小割就是最大独立集的最后剩余的数目。

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+7;
const int maxm=1e6+7;
const int inf=0x3f3f3f3f;
int dx[]={-1,-2,-2,-1,1,2,1,2};
int dy[]={2,1,-1,-2,2,1,-2,-1};
int a[210][210],S,T;
int n,m,x,y;
struct Dinic {
    struct Edge {
        int next, f, to;
    } e[maxm];
    int head[maxn], dep[maxn], tol, ans;
    int cur[maxn];
    int src, sink, n;
    void add(int u, int v, int f) {
        tol++;
        e[tol].to = v;
        e[tol].next = head[u];
        e[tol].f = f;
        head[u] = tol;
        tol++;
        e[tol].to = u;
        e[tol].next = head[v];
        e[tol].f = 0;
        head[v] = tol;
    }

    bool bfs() {
        queue<int> q;
        memset(dep, -1, sizeof(dep));
        q.push(src);
        dep[src] = 0;
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int i = head[now]; i; i = e[i].next) {
                if (dep[e[i].to] == -1 && e[i].f) {
                    dep[e[i].to] = dep[now] + 1;
                    if (e[i].to == sink)
                        return true;
                    q.push(e[i].to);
                }
            }
        }
        return false;
    }

    int dfs(int x, int maxx) {
        if (x == sink)
            return maxx;
        for (int &i = cur[x]; i; i = e[i].next) {
            if (dep[e[i].to] == dep[x] + 1 && e[i].f > 0) {
                int flow = dfs(e[i].to, min(maxx, e[i].f));
                if (flow) {
                    e[i].f -= flow;
                    e[i ^ 1].f += flow;
                    return flow;
                }
            }
        }
        return 0;
    }

    int dinic(int s, int t) {
        ans = 0;
        this->src = s;
        this->sink = t;
        while (bfs()) {
            for (int i = 0; i <= n; i++)
                cur[i] = head[i];
            while (int d = dfs(src, inf))
                ans += d;
        }
        return ans;
    }

    void init(int n) {
        this->n = n;
        memset(head, 0, sizeof(head));
        tol = 1;
    }
} G;

int id(int x,int y){
    return (x-1)*n + y;
}

int main() {

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        a[x][y] = 1;
    }
    S = 0;
    T = n * n + 1;
    G.init(T);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j]) {
                continue;
            }
            int idd = id(i, j);
            if ((i + j) & 1) {
                G.add(S, idd, 1);
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 1 && x <= n && y >= 1 && y <= n) {
                        G.add(idd, id(x, y), 1);
                    }
                }
            } else {
                G.add(idd, T, 1);
            }
        }
    }
    printf("%d
", n * n - m - G.dinic(S, T));
}

最长不下降子序列问题

题目描述

给定正整数序列x1,...,xn 。

（1）计算其最长不下降子序列的长度s。

（2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。

（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的不下降子序列。

设计有效算法完成（1）（2）（3）提出的计算任务。

输入格式

第1 行有1个正整数n，表示给定序列的长度。接下来的1 行有n个正整数n:x1, ..., xn。

输出格式

第1 行是最长不下降子序列的长度s。第2行是可取出的长度为s 的不下降子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的不下降子序列个数。

输入样例

4
3 6 2 5

输出样例

2
2
3

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+7;
const int maxm=1e5+7;
const int inf=0x3f3f3f3f;
int f[600],n,ans,a[600];
struct Dinic {
    struct Edge {
        int next, f, to;
    } e[maxm];
    int head[maxn], dep[maxn], tol, ans;
    int cur[maxn];
    int src, sink, n;

    void add(int u, int v, int f) {
        tol++;
        e[tol].to = v;
        e[tol].next = head[u];
        e[tol].f = f;
        head[u] = tol;
        tol++;
        e[tol].to = u;
        e[tol].next = head[v];
        e[tol].f = 0;
        head[v] = tol;
    }

    bool bfs() {
        queue<int> q;
        memset(dep, -1, sizeof(dep));
        q.push(src);
        dep[src] = 0;
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int i = head[now]; i; i = e[i].next) {
                if (dep[e[i].to] == -1 && e[i].f) {
                    dep[e[i].to] = dep[now] + 1;
                    if (e[i].to == sink)
                        return true;
                    q.push(e[i].to);
                }
            }
        }
        return false;
    }

    int dfs(int x, int maxx) {
        if (x == sink)
            return maxx;
        for (int &i = cur[x]; i; i = e[i].next) {
            if (dep[e[i].to] == dep[x] + 1 && e[i].f > 0) {
                int flow = dfs(e[i].to, min(maxx, e[i].f));
                if (flow) {
                    e[i].f -= flow;
                    e[i ^ 1].f += flow;
                    return flow;
                }
            }
        }
        return 0;
    }

    int dinic(int s, int t) {
        ans = 0;
        this->src = s;
        this->sink = t;
        while (bfs()) {
            for (int i = 0; i <= n; i++)
                cur[i] = head[i];
            while (int d = dfs(src, inf))
                ans += d;
        }
        return ans;
    }

    void init(int n) {
        this->n = n;
        memset(head, 0, sizeof(head));
        tol = 1;
    }
} G;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] <= a[i]) {
                f[i] = max(f[i], f[j] + 1);
                ans = max(f[i], ans);
            }
        }
    }
    G.init(n * 2 + 3);
    printf("%d
", ans);
    for (int i = 1; i <= n; i++) {
        G.add(i + 2, i + n + 2, 1);
        if (f[i] == 1) {
            G.add(1, i + 2, 1);
        }
        if (f[i] == ans) {
            G.add(i + n + 2, 2, 1);
        }
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i] && f[j] + 1 == f[i]) {
                G.add(j + n + 2, i + 2, 1);
            }
        }
    }
    int len=ans;
    ans=G.dinic(1, 2);
    printf("%d
", ans);
    G.add(1, 3, inf);
    G.add(3, 1 + n + 2, inf);
    if (f[n] == len && n != 1) {
        G.add(n + n + 2, 2, inf);
        G.add(n + 2, 2+n + n, inf);
    }
    printf("%d
", ans + G.dinic(1, 2));
}