【BZOJ4808】马
Description
众所周知，马后炮是中国象棋中很厉害的一招必杀技。"马走日字"。本来，如果在要去的方向有别的棋子挡住（俗称"蹩马腿"），则不允许走过去。为了简化问题，我们不考虑这一点。马跟马显然不能在一起打起来，于是rly在一天再次借来了许多许多的马在棋盘上摆了起来……但这次，他实在没兴趣算方案数了，所以他只想知道在N×M的矩形方格中摆马使其互不吃到的情况下的最多个数。但是，有一个很不幸的消息，rly由于玩得太Happy，质量本来就不好的棋盘被rly弄坏了，不过幸好只是破了其中的一些格子（即不能再放子了），问题还是可以继续解决的。
Input
一行，两个正整数N和M。
接下来N行，每行M个数，要么为0，表示没坏，要么为1，表示坏了。
N<=200,M<=200
Output
一行，输出最多的个数。
Sample Input
2 3
0 1 0
0 1 0
0 1 0
0 1 0
Sample Output
2
题解：黑白染色，然后无脑最小割~
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define num(A,B) ((A)*m-m+B)
#define ok(A,B) (A>=1&&A<=n&&B>=1&&B<=m&&!map[A][B])
using namespace std;
int n,m,cnt,tot,ans;
int dx[]={-1,-1,1,1,-2,-2,2,2},dy[]={2,-2,2,-2,1,-1,1,-1};
int d[40010],next[500010],val[500010],head[40010],to[500010],map[210][210];
queue<int> q;
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
to[cnt]=a,val[cnt]=0,next[cnt]=head[b],head[b]=cnt++;
}
int dfs(int x,int mf)
{
if(x==n*m+1) return mf;
int i,k,temp=mf;
for(i=head[x];i!=-1;i=next[i])
{
if(d[to[i]]==d[x]+1&&val[i])
{
k=dfs(to[i],min(mf,val[i]));
if(!k) d[to[i]]=0;
val[i]-=k,val[i^1]+=k,temp-=k;
if(!temp) break;
}
}
return mf-temp;
}
int bfs()
{
memset(d,0,sizeof(d));
while(!q.empty()) q.pop();
int i,u;
d[0]=1,q.push(0);
while(!q.empty())
{
u=q.front(),q.pop();
for(i=head[u];i!=-1;i=next[i])
{
if(val[i]&&!d[to[i]])
{
d[to[i]]=d[u]+1;
if(to[i]==n*m+1) return 1;
q.push(to[i]);
}
}
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,k,a;
memset(head,-1,sizeof(head));
for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&map[i][j]);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(map[i][j]) continue;
tot++;
if((i^j)&1)
{
add(0,num(i,j),1);
for(k=0;k<8;k++) if(ok(i+dx[k],j+dy[k])) add(num(i,j),num(i+dx[k],j+dy[k]),1<<30);
}
else add(num(i,j),n*m+1,1);
}
}
while(bfs()) ans+=dfs(0,1<<30);
printf("%d",tot-ans);
return 0;
}
【BZOJ3175】[Tjoi2013]攻击装置
题解：同上题
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define num(A,B) ((A-1)*n+B)
#define ok(A,B) (A>=1&&A<=n&&B>=1&&B<=n&&str[A][B-1]=='0')
using namespace std;
int n,cnt,tot,ans,S,T;
int dx[]={-1,-1,1,1,-2,-2,2,2},dy[]={2,-2,2,-2,1,-1,1,-1};
int d[40010],next[500010],val[500010],head[40010],to[500010];
char str[210][210];
queue<int> q;
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
to[cnt]=a,val[cnt]=0,next[cnt]=head[b],head[b]=cnt++;
}
int dfs(int x,int mf)
{
if(x==T) return mf;
int i,k,temp=mf;
for(i=head[x];i!=-1;i=next[i])
{
if(d[to[i]]==d[x]+1&&val[i])
{
k=dfs(to[i],min(mf,val[i]));
if(!k) d[to[i]]=0;
val[i]-=k,val[i^1]+=k,temp-=k;
if(!temp) break;
}
}
return mf-temp;
}
int bfs()
{
memset(d,0,sizeof(d));
while(!q.empty()) q.pop();
int i,u;
d[S]=1,q.push(S);
while(!q.empty())
{
u=q.front(),q.pop();
for(i=head[u];i!=-1;i=next[i])
{
if(val[i]&&!d[to[i]])
{
d[to[i]]=d[u]+1;
if(to[i]==T) return 1;
q.push(to[i]);
}
}
}
return 0;
}
int main()
{
scanf("%d",&n);
int i,j,k;
S=0,T=n*n+1;
memset(head,-1,sizeof(head));
for(i=1;i<=n;i++) scanf("%s",str[i]);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(str[i][j-1]=='1') continue;
tot++;
if((i^j)&1)
{
add(S,num(i,j),1);
for(k=0;k<8;k++) if(ok(i+dx[k],j+dy[k])) add(num(i,j),num(i+dx[k],j+dy[k]),1<<30);
}
else add(num(i,j),T,1);
}
}
while(bfs()) ans+=dfs(0,1<<30);
printf("%d",tot-ans);
return 0;
}