Submission #38075662

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
int S,T,N;
const int NUM = 90105;
const int INF = 987654321;
int dis[NUM], inq[NUM], work[NUM], vis[NUM];
pii pre[NUM];
vector<vector<int> > v, C, F, cost, rev;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
string mp[301];

bool spfa(){
	for(int i=0;i<N;i++){
		dis[i]=INF;
		pre[i]={i,-1};
		inq[i]=0;
        work[i]=0;
        vis[i]=0;
	}
	dis[S]=0;
	queue<int> q;
	q.push(S);
	inq[S]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		inq[x]=0;
		for(int i=0;i<(int)v[x].size();i++){
			int nx = v[x][i];
            if(C[x][i]>F[x][i]&&dis[nx]>dis[x]+cost[x][i]){
				dis[nx]=dis[x]+cost[x][i];
				pre[nx]={x,i};
				if(!inq[nx]){
					q.push(nx);
					inq[nx]=1;
				}
			}
		}
	}
	return pre[T].first!=T;
}
bool update(){
    int Min = INF;
    for(int x=0;x<N;x++){
        if(!vis[x]) continue;
        for(int i=0;i<(int)v[x].size();i++){
            int nx = v[x][i];
            if(C[x][i]>F[x][i]&&!vis[nx]){
				Min = min(Min,dis[x] + cost[x][i] - dis[nx]);
			}
        }
    }
    if(Min>=INF) return false;
    for(int x=0;x<N;x++) if(!vis[x]) dis[x] += Min;
    return true;
}
pii sol(int x, int f){
    vis[x] = 1;
    if(x==T) return {f,0};
    for(int &i=work[x];i<(int)v[x].size();i++){
		int nx=v[x][i];
        int j = rev[x][i];
		if(!vis[nx] && C[x][i]>F[x][i] && (true?dis[nx]==dis[x]+cost[x][i]:pre[nx].first == x)){
			auto [ret,retcost] = sol(nx,min(C[x][i]-F[x][i],f));
			if(ret>0){
				F[x][i]+=ret;
				F[nx][j]-=ret;
				return {ret,retcost+cost[x][i]};
			}
		}
	}
	
	return {0,0};
}
void addEdge(int a, int b, int c, int d){
    v[a].push_back(b);
    v[b].push_back(a);
    C[a].push_back(c);
    C[b].push_back(0);
    F[a].push_back(0);
    F[b].push_back(0);
    cost[a].push_back(d);
    cost[b].push_back(-d);
    rev[a].push_back((int)v[b].size()-1);
    rev[b].push_back((int)v[a].size()-1);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;cin>>n>>m;
    S=0;
    T=n*m+1;
    N=n*m+2;
    v.resize(N);
    C.resize(N);
    F.resize(N);
    cost.resize(N);
    rev.resize(N);
    int goal = 0;
    for(int i=0;i<n;i++){
        cin>>mp[i];
        for(int j=0;j<m;j++){
            goal += mp[i][j]=='2';
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]=='1') continue;
            int vn = i*m+j+1;
            if((i+j)%2){
                addEdge(S,vn,1,0);
                if(mp[i][j]=='2'){
                    goal++;
                }
                for(int k=0;k<4;k++){
                    int ni=i+dx[k], nj=j+dy[k];
                    if(0<=ni&&ni<n&&0<=nj&&nj<m){
                        if(mp[i][j]=='?' && mp[ni][nj]=='?') continue;
                        int nvn = ni*m+nj+1;
                        addEdge(vn,nvn,1,mp[i][j]=='2' && mp[ni][nj]=='2'?-1:1);
                    }
                }
            }
            else addEdge(vn,T,1,0);
        }
    }
    int ans = 0, anscost = 0;
    spfa();
    do{
        bool isok = false;
        for(int i=0;i<N;i++) work[i]=0;
       	do{
            for(int i=0;i<N;i++) vis[i]=0;
            auto [cnt,cost] = sol(S,INF);
            anscost += cnt;
            ans = max(ans, anscost);
            isok = cnt>0;
        }while(isok);
    }while(update());
    bool isok = true;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]!='2') continue;
            int vn = i*m+j+1;
            if((i+j)%2){
                for(int i=0;i<(int)v[S].size();i++){
                    if(v[S][i] == vn) isok &= F[S][i]>0;
                }
            }
            else{
                for(int i=0;i<(int)v[vn].size();i++){
                    if(v[vn][i] == T) isok &= F[vn][i]>0;
                }
            }
        }
    }
    cout<<(isok?"Yes":"No");
}

Submission Info

Judge Result