看上去毫无问题的做法可能是完全错误的

跟着出(大)题(毒)人(瘤)的思路走是最危险的

懵逼的 题目

/kel

扯淡的 题解

我们发现 这题居然不能直接按照题目给的图来跑最大流…

因为会出现$A_1 \to B_2$或者$B_1 \to A_2$的情况

那么怎么避免啊…

我们跑完第一次最大流判定通过之后, 调换$B_1, B2$, 然后再跑一次, 如果都通过了, 才给出”Yes”…

画一下图就明白了…

  • $A_1 \to B_2$: 那么$S \to B_1$的容量小于$B_2 \to T$的容量, 调换之后不可能会出现大容量到小流量还要加一个$A\to B_2$的流量的情况
  • $B_1\to A_2 $: 那么$S\to B_1$的容量大于$B_2 \to T$的容量, 调换之后也不可能再流出东西了

(假装是个严谨的证明

沙茶的 代码

注意按照他的邻接矩阵建图的时候也要加反向边…

/**************************************************************
    Problem: 3504
    User: Cansult
    Language: C++
    Result: Accepted
    Time:104 ms
    Memory:21604 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define MAXL (100 + 5)
#define INF (0x7ffffff)
#define rev(i) ((((i) - 1) ^ 1) + 1)
using namespace std;
const int s = 0, t = MAXN - 1;
struct edg
{
    int from, to, next, cap, flow;
}b[MAXM << 1];
int g[MAXN], cntb, n, m, dis[MAXN];
void adn(int from, int to, int cap)
{
    b[++cntb].next = g[from];
    b[cntb].from = from, b[cntb].to = to, b[cntb].cap = cap;
    g[from] = cntb;
}
int dinic(int dq, int maxf)
{
    if (dq == t || !maxf)
        return maxf;
    int re = 0;
    for (int i = g[dq]; i; i = b[i].next)
        if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
        {
            int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
            maxf -= zl;
            re += zl;
        }
    return re;
} 
bool bfs()
{
    queue<int> q;
    q.push(s);
    memset(dis, 0, sizeof(dis));
    dis[s] = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
            if (!dis[b[i].to] && b[i].cap > b[i].flow)
                dis[b[i].to] = dis[dq] + 1, q.push(b[i].to);
    }
    return dis[t] > 0;
}
int solve()
{
    int re = 0;
    while (bfs())
        re += dinic(s, INF);
    return re;
}
int main()
{
    int s1, t1, s2, t2, f1, f2;
    while (scanf("%d%d%d%d%d%d%d", &n, &s1, &t1, &f1, &s2, &t2, &f2) == 7)
    {
        ++s1, ++t1, ++s2, ++t2;
        f1 <<= 1, f2 <<= 1;
        memset(g, 0, sizeof(g));
        cntb = 0;
        char srs[MAXL];
        adn(s, t1, 0), adn(t1, s, 0);
        adn(s1, t, 0), adn(t, s1, 0);
        adn(s, s1, f1), adn(s1, s, 0);
        adn(s, s2, f2), adn(s2, s, 0);
        adn(t1, t, f1), adn(t, t1, 0);
        adn(t2, t, f2), adn(t, t2, 0);
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", srs);
            for (int j = 1; j <= n; j++)
                if (srs[j - 1] == 'N')
                    adn(i, j, INF), adn(j, i, 0);
                else if (srs[j - 1] == 'O')
                    adn(i, j, 2), adn(j, i, 0);
        }
        for (int i = 1; i <= cntb; i++)
            b[i].flow = 0;
        if (solve() != f1 + f2)
        {
            puts("No");
            continue;
        }
        b[1].cap = b[3].cap = f1;
        b[5].cap = b[9].cap = 0;
        for (int i = 1; i <= cntb; i++)
            b[i].flow = 0;
        if (solve() != f1 + f2)
        {
            puts("No");
            continue;
        }
        puts("Yes");
    }
    return 0;
}

By 沙茶 Cansult