这是一个二分图（其实怎么证这是个二分图…），求最大独立集=n-最大匹配
code：
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;void up(int &x,int y){if(x<y)x=y;}void down(int &x,int y){if(x>y)x=y;}const int dx[8]={-1,-2,1,2,-1,-2,1,2};const int dy[8]={-2,-1,-2,-1,2,1,2,1};const int maxn = 51000;const int maxl = 210;struct edge{ int y,nex; edge(){} edge(int _y,int _nex){y=_y;nex=_nex;}}a[maxn<<4]; int len,fir[maxn];void ins(int x,int y){a[++len]=edge(y,fir[x]); fir[x]=len;}int n,N;int id[maxl][maxl];char s[1100];int match[maxn];bool v[maxn]; int q[maxn],tail;bool vis[maxn];bool find_(int x){ if(v[x]) return false; v[x]=true; q[tail++]=x; for(int k=fir[x];k;k=a[k].nex) { int y=a[k].y; if(!match[y]||find_(match[y])) { match[y]=x; return true; } } return false;}int solve(){ int r=0; memset(match,0,sizeof match); memset(v,false,sizeof v); for(int i=1;i<=N;i++) { tail=0; if(vis[i]&&find_(i)) r++; while(tail--) v[q[tail]]=false; } return r;}void dfs(int x,int d){ v[x]=true; if(d) vis[x]=true; for(int k=fir[x];k;k=a[k].nex) { int y=a[k].y; if(!v[y]) dfs(y,d^1); }}int main(){ memset(fir,0,sizeof fir); len = 0; memset(id,0,sizeof id); scanf("%d",&n); N=0; for(int i=1;i<=n;i++) { scanf("%s",s); for(int j=0;j<n;j++) if(s[j]=='0') id[i][j+1]=++N; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int t=id[i][j]; if(t) { for(int k=0;k<8;k++) { int x=i+dx[k],y=j+dy[k]; if(x>0&&y>0&&id[x][y]) ins(t,id[x][y]); } } } } memset(v,false,sizeof v); memset(vis,false,sizeof v); for(int i=1;i<=N;i++) if(!v[i]) dfs(i,1); PRintf("%d/n",N-solve()); return 0;}新闻热点
疑难解答
