题目地址：洛谷：【P3163】[CQOI2014]危桥 – 洛谷、BZOJ：Problem 3504. — [Cqoi2014]危桥

题目描述

Alice和Bob居住在一个由N座岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路是双向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。Alice希望在岛屿a1和a2之间往返an次（从al到a2再从a2到al算一次往返）。同时，Bob希望在岛屿b1和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问Alice和Bob能完成他们的愿望吗？

题意简述

给你一个图，有的边可以走任意次有的只能走两次。求是否能在a1和a2两个点间往返an次且能在b1和b2两个点间往返bn次。

输入输出格式

输入格式：
本题有多组测试数据。每组数据第一行包含7个空格隔开的整数，分别为N、a1、a2、an、b1、b2、bn。接下来是一个N行N列的对称矩阵，由大写字母组成。矩阵的i行j列描述编号i一1和j-l的岛屿间的连接情况，若为”O“则表示有危桥相连：为”N“表示有普通的桥相连：为”X“表示没有桥相连。

输出格式：
对于每组测试数据输出一行，如果他们都能完成愿望输出”Yes“，否则输出”No“。

输入输出样例

输入样例#1：

4 0 1 1 2 3 1
XOXX
OXOX
XOXO
XXOX
4 0 2 1 1 3 2
XNXO
NXOX
XOXO
OXOX

输出样例#1：

Yes
No

说明

4<=N<50
0<=a1, a2, b1, b2<=N-1
1 <=an. b<=50

题解

是不是很像网络流，建图跑就是了。
但是有a1流去b2、b1流去a2的情况，这时只要把a1和b2接到源上，a2和b1接到汇上重新检验就可以了。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

const int MAXN = 55, INF = 1e9;

int n;

struct Edge {
    int to, cap, nxt;
} gra[MAXN * MAXN << 1], grab[MAXN * MAXN << 1];
int head[MAXN], headb[MAXN], tot;

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int level[MAXN];

inline bool bfs(int s, int t) {
    std::queue<int> que;
    memset(level, -1, sizeof(level));
    level[s] = 0; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(level[v] == -1 && gra[i].cap) {
                level[v] = level[u] + 1;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || !left) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(level[v] == level[u] + 1 && gra[i].cap) {
            int f = dfs(v, t, std::min(left, gra[i].cap));
            if(f) {
                flow += f; left -= f; gra[i].cap -= f; gra[i ^ 1].cap += f;
                if(!left) return flow;
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) flow += f;
    }
    return flow;
}

int a1, a2, an, b1, b2, bn, S, T;
char tmp[MAXN];

int main() {
    while(scanf("%d", &n) != EOF) {
        memset(head, -1, sizeof(head)); tot = 0;
        S = n + 1; T = S + 1;
        scanf("%d%d%d%d%d%d", &a1, &a2, &an, &b1, &b2, &bn);
        a1++; a2++; b1++; b2++;
        for(int i = 1; i <= n; i++) {
            scanf("%s", tmp + 1);
            for(int j = 1; j <= n; j++) {
                if(tmp[j] == 'O') {
                    addedge(i, j, 2);
                } else if(tmp[j] == 'N') {
                    addedge(i, j, INF);
                }
            }
        }
        memcpy(grab, gra, sizeof(gra));
        memcpy(headb, head, sizeof(head));
        addedge(S, a1, an << 1); addedge(S, b1, bn << 1);
        addedge(a2, T, an << 1); addedge(b2, T, bn << 1);
        if(dinic(S, T) < (an + bn) << 1) {
            puts("No"); continue;
        }
        memcpy(gra, grab, sizeof(gra));
        memcpy(head, headb, sizeof(head));
        addedge(S, a1, an << 1); addedge(S, b2, bn << 1);
        addedge(a2, T, an << 1); addedge(b1, T, bn << 1);
        if(dinic(S, T) < (an + bn) << 1) {
            puts("No"); continue;
        }
        puts("Yes");
    }
    return 0;
}