【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

Sample Output

题解：黑白染色，然后无脑最小割~

#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;

}

巴特西

【BZOJ4808/3175】马/[Tjoi2013]攻击装置最小割

【BZOJ4808】马

Description

Input

Output

Sample Input

Sample Output

【BZOJ3175】[Tjoi2013]攻击装置

最新文章

热门文章

巴特西

【BZOJ4808/3175】马/[Tjoi2013]攻击装置 最小割

【BZOJ4808】马

Description

Input

Output

Sample Input

Sample Output

【BZOJ3175】[Tjoi2013]攻击装置

最新文章

热门文章

【BZOJ4808/3175】马/[Tjoi2013]攻击装置最小割