二分图求最大独立点集
本问题在二分图中已处理过,此处用dinic写了一遍
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN=40005,MAXM=5000005;
int s,t,head[MAXN],nume,ma[205][205],dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={2,1,-1,-2,2,1,-1,-2},dep[MAXN],cur[MAXN],n,m,maxflow;
struct edge{
int to,nxt,cap,flow;
}e[MAXM];
void adde(int from,int to,int cap){
e[++nume].to=to;
e[nume].nxt=head[from];
e[nume].cap=cap;
head[from]=nume;
}
queue<int>q;
bool bfs(){
memset(dep,0,sizeof(dep));
q.push(s);dep[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dep[v]&&e[i].flow<e[i].cap){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t];
}
int dfs(int u,int flow){
if(u==t) return flow;
int tot=0;
for(int &i=cur[u];i&&tot<flow;i=e[i].nxt){
int v=e[i].to;
if(dep[v]==dep[u]+1&&e[i].flow<e[i].cap){
if(int t=dfs(v,min(flow-tot,e[i].cap-e[i].flow))){
e[i].flow+=t;
e[((i-1)^1)+1].flow-=t;
tot+=t;
}
}
}
return tot;
}
void dinic(){
while(bfs()){
for(int i=s;i<=t;i++) cur[i]=head[i];
maxflow+=dfs(s,0x3f3f3f3f);
}
}
int main(){
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ma[i][j]=++cnt;
}
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
ma[u][v]=0;
}
s=0;t=cnt+1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ma[i][j]){
if((i+j)&1) adde(s,ma[i][j],1),adde(ma[i][j],s,0);
else adde(ma[i][j],t,1),adde(t,ma[i][j],0);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ma[i][j]&&((i+j)&1)){
for(int k=0;k<8;k++){
int x=i+dx[k],y=j+dy[k];
if(x>0&&x<=n&&y>0&&y<=n){
adde(ma[i][j],ma[x][y],1);
adde(ma[x][y],ma[i][j],0);
}
}
}
}
}
dinic();
cout<<cnt-maxflow-m<<endl;
return 0;
}