二分图匹配练习题(最大独立集)
算法1 匈牙利算法
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=110;
int n,m,k;
bool g[N][N],st[N][N];
PII match[N][N];
int dx[]={-2,-1,1,2,2,1,-1,-2};
int dy[]={1,2,2,1,-1,-2,-2,-1};
bool find(int x,int y)
{
for(int i=0;i<8;++i)
{
int a=x+dx[i],b=y+dy[i];
if(a<1||a>n||b<1||b>m||st[a][b]||g[a][b]) continue;
st[a][b]=true;
PII t=match[a][b];
if(!t.x||find(t.x,t.y))
{
match[a][b]={x,y};
return true;
}
}
return false;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<k;++i)
{
int a,b;
scanf("%d%d",&a,&b);
g[a][b]=true;
}
int res=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
if(g[i][j]||(i+j)%2) continue;
memset(st,0,sizeof st);
if(find(i,j)) ++res;
}
printf("%d",n*m-k-res);
return 0;
}
算法2 最大流
#include<iostream>
#include<cstring>
using namespace std;
const int N=10010,M=100010,INF=2e9;
int n,m,k,S,T;
int h[N],e[M],f[M],ne[M],idx;
int q[N],d[N],cur[N];
int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={1,2,2,1,-1,-2,-2,-1};
bool g[110][110];
int get(int x,int y)
{
return (x-1)*m+y;
}
void add(int a,int b,int c)
{
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
memset(d,-1,sizeof d);
int hh=0,tt=0;
q[0]=S,d[S]=0,cur[S]=h[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int ver=e[i];
if(d[ver]==-1&&f[i])
{
d[ver]=d[t]+1;
cur[ver]=h[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
cur[u]=i;
int ver=e[i];
if(d[ver]==d[u]+1&&f[i])
{
int t=find(ver,min(f[i],limit-flow));
if(!t) d[ver]=-1;
f[i]-=t,f[i^1]+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs()) while(flow=find(S,INF)) res+=flow;
return res;
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d%d",&n,&m,&k);
S=0,T=n*m+1;
while(k--)
{
int a,b;
scanf("%d%d",&a,&b);
g[a][b]=true;
}
int tot=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
if(g[i][j]) continue;
if(i+j&1)
{
add(S,get(i,j),1);
for(int k=0;k<8;++k)
{
int x=i+dx[k],y=j+dy[k];
if(x>=1&&x<=n&&y>=1&&y<=m)
add(get(i,j),get(x,y),1);
}
}
else add(get(i,j),T,1);
++tot;
}
printf("%d",tot-dinic());
return 0;
}