牛客多校第三场-D-Ama no Jaku

zhujio / 2023-07-31 / 原文

D-Ama no Jaku_2023牛客暑期多校训练营3

做法：2-sat

先贴个代码，晚点补上思路

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N=2e3+5;

char a[N][N];

std::vector<int>edge[N];

//bel数组记录某个点在哪个连通块里面
int dfn[N],low[N],ins[N],bel[N],sz[N],sum[N],idx,cnt,n;
stack<int>stk;

void dfs(int u){
    dfn[u]=low[u]=++idx;
    ins[u]=true;
    stk.push(u);
    for(auto v:edge[u]){
        if(!dfn[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }else{
            if(ins[v])low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        cnt++;
        while(1){
            int v=stk.top();
            ins[v]=false;
            bel[v]=cnt;
            stk.pop();
            sum[cnt]++;
            if(v>2*n)sz[cnt]++;
            if(v==u)break;
        }
    }
}

int calc(int val){
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(bel,0,sizeof(bel));
    memset(sum,0,sizeof(sum));
    memset(sz,0,sizeof(sz));
    idx=cnt=0;
    for(int i=1;i<=4*n;i++)edge[i].clear();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]-'0'==val){
                edge[i].push_back(j+n);
                edge[j+n].push_back(i);
                edge[i+2*n].push_back(j+3*n);
                edge[j+3*n].push_back(i+2*n);
            }else{
                edge[i].push_back(j+3*n);
                edge[j+3*n].push_back(i);
                edge[j+n].push_back(i+2*n);
                edge[i+2*n].push_back(j+n);
            }
        }
    }
    for(int i=1;i<=4*n;i++){
        if(!dfn[i])dfs(i);
    }
    for(int i=1;i<=2*n;i++){
        if(bel[i]==bel[i+2*n])return INT_MAX;
    }
    int ans=0;
    for(int i=1;i<=cnt;i++)ans+=min(sum[i]-sz[i],sz[i]);
    return ans;
}

int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    int ans=min(calc(0),calc(1));
    if(ans<INT_MAX)cout<<ans/2<<endl;
    else cout<<-1<<endl;
    return 0;
}