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; }标签:cnt,no,Ama,memset,int,dfn,low,sizeof,第三场 From: https://www.cnblogs.com/zhujio/p/17592742.html