最大流，反复跑流

题意：

分析：

这题我不会，是看人题解后做的。汗

这题有两个收获：
1.网络流建无向图。

void add(int from, int to, int cap) {
    E[cnt].to = to;
    E[cnt].cap = cap;
    E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];
    head[from] = cnt++;
    E[cnt].to = from;
    E[cnt].cap = cap;           //有向图 为 0
    E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];
    head[to] = cnt++;
}

2.反复跑图：
为什么先跑一遍a1,a1 到 b1,b2
然后再交换一下b1,b2就可以了呢？
推荐这篇博客：https://www.cnblogs.com/chenyushuo/p/5139556.html

代码如下，面向结果编程：

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int inf = 2e9;
const int max_n = 55;
const int max_m = max_n * max_n;
int n, m;
char ma[max_n][max_n];

struct edge
{
    int to, cap, rev, next;
}E[max_m * 2];
int head[max_n * 2];
int cnt = 1;
void add(int from, int to, int cap) {
    E[cnt].to = to;
    E[cnt].cap = cap;
    E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];
    head[from] = cnt++;
    E[cnt].to = from;
    E[cnt].cap = cap;           //有向图 为 0
    E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];
    head[to] = cnt++;
}
void init() {
    fill(head, head + n + 10, false);
    cnt = 1;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j < i;j++)
            if (ma[i][j] == 'O')add(i, j, 2);
            else if (ma[i][j] == 'N') add(i, j, inf);
}

int iter[max_n * 2];
int dist[max_n * 2];
bool searchpath(int s, int t) {
    fill(dist, dist + max_n * 2, -1);
    queue<int> que;dist[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (dist[e.to] != -1 || e.cap == 0)continue;
            dist[e.to] = dist[u] + 1;
            que.push(e.to);
        }
    }return dist[t] != -1;
}

int matchpath(int u, int t, int f) {
    if (u == t)return f;
    for (int& i = iter[u];i;i = E[i].next) {
        edge& e = E[i];
        if (dist[e.to] <= dist[u] || e.cap <= 0)continue;
        int d = matchpath(e.to, t, min(e.cap, f));
        if (d > 0) {
            e.cap -= d;
            E[e.rev].cap += d;
            return d;
        }
    }return false;
}

int dinic(int s, int t) {
    int flow = 0;int f;
    while (searchpath(s, t)) {
        for (int i = 1;i < max_n * 2;i++)iter[i] = head[i];
        while (f = matchpath(s, t, inf))
            flow += f;
    }return flow;
}

int main() {
    ios::sync_with_stdio(0);
    int a1, a2, b1, b2, an, bn;
    while (cin >> n >> a1 >> a2 >> an >> b1 >> b2 >> bn) {
        a1++;a2++;b1++;b2++;an <<= 1;bn <<= 1;
        int start = n + 1;int ed = start + 1;
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= n;j++)
                cin >> ma[i][j];
        init();
        add(start, a1, an);add(start, b1, bn); 
        add(a2, ed, an);add(b2, ed, bn);
        if (dinic(start, ed) != an + bn)cout << "No\n";
        else {
            init();
            add(start, a1, an);add(a2, ed, an);
            add(start, b2, bn);add(b1, ed, bn);
            if (dinic(start, ed) == an + bn)cout << "Yes\n";
            else cout << "No\n";
        }
    }
}