C++(g++ 7.5.0) 解法, 执行用时: 5ms, 内存消耗: 788K, 提交时间: 2022-12-28 15:00:41

#include<bits/stdc++.h>
using namespace std;
const int N = 10010, M = 200010, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], f[M], idx, d[N], n, a1, a2, an, b1, b2, bn, S, T, cur[M], H[N], p[N];
vector<int>num[N];
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
    e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++; 
}

int find(int x)
{
	if(p[x] != x) return p[x] = find(p[x]);
	return p[x];
}
bool bfs()
{
    queue<int>q;
    memset(d, -1, sizeof d);
    q.push(S);
    d[S] = 0;
    cur[S] = h[S];
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if((d[j] == -1) && f[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j == T) return true;
                q.push(j);
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        int j = e[i];
        cur[u] = i;
        if((d[j] == d[u] + 1) && f[i])
        {
            int t = find(j, min(f[i], limit - flow));
            if(!t) d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while(bfs()) while(flow = find(S, 0x3f3f3f3f)) r += flow;
    	
    return r;
}
char g[55][55];

void build()
{
	memset(h, -1, sizeof h);
	idx = 0;
	add(S, a1, 2 * an);
	add(S, b1, 2 * bn);
	add(a2, T, 2 * an);
	add(b2, T, 2 * bn);
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= n; j ++ )
			if(g[i][j] == 'N') add(i, j, INF);
		else if(g[i][j] == 'O') add(i, j, 2);
}
int main()
{
	while(cin >> n >> a1 >> a2 >> an >> b1 >> b2 >> bn)
	{
		S = 0, T = n + 1;
        a1 ++, a2 ++, b1 ++, b2 ++;
		for(int i = 1; i <= n; i ++ ) cin >> g[i] + 1;

		build();
		if(dinic() == 2 * an + 2 * bn)
		{
			swap(b1, b2);
			build();
			if(dinic() == 2 * an + 2 * bn) cout << "Yes\n";
			else cout << "No\n"; 
		}
		else cout << "No\n";
	}

}

C++ 解法, 执行用时: 9ms, 内存消耗: 432K, 提交时间: 2022-01-24 20:40:14

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 100,M = N*N,inf = 0x3f3f;
int h[N],ne[M],e[M],f[M],idx;
void add(int a,int b,int c){
    ne[idx] = h[a],e[idx] = b,f[idx] = c,h[a] = idx++;
    ne[idx] = h[b],e[idx] = a,f[idx] = 0,h[b] = idx++;
}
int pre[N],a[N];
char mp[N][N];
int n,a1,a2,a3,b1,b2,b3;
int EK(int s,int t){
    int flow = 0;
    while(1){
        memset(a,0,sizeof a);
        queue<int> q;
        q.push(s);
        a[s] = inf;
        while(!q.empty()){
            int u = q.front();q.pop();
            for(int i = h[u];~i;i=ne[i]){
                int y = e[i];
                if(f[i] > 0 && !a[y]){
                    a[y] = min(a[u],f[i]);
                    pre[y] = i;
                    q.push(y);
                }
            }
            if(a[t])break;
        }
        if(!a[t])break;
        for(int i = t;i!=s;i=e[pre[i]^1]){
            f[pre[i]] -= a[t];
            f[pre[i]^1] += a[t];
        }
        flow += a[t];
    }
    return flow;
}
bool solve(int x1,int x2,int y1,int y2){
    memset(h,-1,sizeof h);
    idx = 0;
    int s = n+1,t = n+2;
    add(s,x1,a3),add(x2,t,a3);
    add(s,y1,b3),add(y2,t,b3);
    for(int i = 0;i<n;i++)
        for(int j = 0;j<n;j++)
            if(mp[i][j] == 'O')add(i,j,1);
            else if(mp[i][j] == 'N')add(i,j,inf);
    return EK(s,t) == a3+b3;
}
int main(){
    while(~scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&a3,&b1,&b2,&b3)){
        for(int i = 0;i<n;i++)
            for(int j = 0;j<n;j++)
               cin >> mp[i][j];
        if(solve(a1,a2,b1,b2) && solve(a1,a2,b2,b1))cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}