题目大意:

求目标图案能否用这样的图形拼出来

链接:http://codeforces.com/gym/100729/attachments/download/3754/20112012-northwestern-european-regional-contest-nwerc-2011-en.pdf

解法:网络流

建立s和t

对于第奇数行白的建在图的左边,偶数行白的在右边

那么..

中间连着所有的黑点

形成了大概长这个样子的图...

就是这样的,直接最大流一遍即可..

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    int weight;
    edge * next;
    edge * anti;
};
const int maxn=500005;
const int inf=99999999;
edge * li[maxn];
int top=0;
edge * new_edge()
{
    static edge a[4000005];
    return &a[top++];
}
edge * inserts(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
    return t;
}
void insert_edge(int x,int y,int z)
{
    edge * t1=inserts(x,y,z);
    edge * t2=inserts(y,x,z);
    t1->anti=t2;
    t2->anti=t1;
}
int dist[maxn];
bool bfs(int s,int t)
{
    memset(dist,-1,sizeof(dist));
    dist[s]=0;
    int front=0,rail=1;
    static int que[maxn];
    que[0]=s;
    for (;front<rail;front++)
    {
        int now=que[front];
        edge * x;
        for (x=li[now];x!=0;x=x->next)
        {
            if ((dist[x->y]==-1)&&(x->weight>0))
            {
                dist[x->y]=dist[now]+1;
                if (x->y==t) return true;
                que[rail++]=x->y;
            }
        }
    }
    return false;
}
int max_flow(int s,int t)
{
    int tot=0;
    static edge * cur[maxn];
    static edge * path[maxn];
    static int pre[maxn];
    for (;bfs(s,t);)
    {
        memset(pre,-1,sizeof(pre));
        memset(path,0,sizeof(path));
        memcpy(cur,li,sizeof(cur));
        int now=s;
        for (;dist[s]!=-1;)
        {
            if (now==t)
            {
                int min_ans=inf;
                int temp=now;
                for (;temp!=s;temp=pre[temp])
                {
                    min_ans=min(min_ans,path[temp]->weight);
                }
                tot+=min_ans;
                temp=now;
                for (;temp!=s;temp=pre[temp])
                {
                    path[temp]->weight-=min_ans;
                    path[temp]->anti->weight+=min_ans;
                }
                now=s;
            }
            edge * x;
            for (x=cur[now];x!=0;x=x->next) 
            {
                if ((dist[x->y]==dist[now]+1)&&(x->weight>0))
                {
                    pre[x->y]=now;
                    path[x->y]=x;
                    cur[now]=x;
                    now=x->y;
                    break;
                }
            }
            if (x==0)
            {
                dist[now]=-1;
                now=pre[now];
            }
        }
    }
    return tot;
}
int n,m;
bool vaild(int x,int y)
{
    return ((x<n)&&(y<m)&&(x>=0)&&(y>=0));
}
int get_id(int x,int y)
{
    return x*m+y;
}
char a[505][505];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        scanf("%d%d",&n,&m);
        int i,j;
        int sum_b=0,sum_w=0;
        for (i=0;i<n;i++)
        {
            scanf("%s",a[i]);
        }
        int s=n*m*2;
        int t=n*m*2+1;
        memset(li,0,sizeof(li));
        top=0;
        for (i=0;i<n;i++)
        {
            for (j=0;j<m;j++)
            {
                if (a[i][j]=='W')
                {
                    sum_w++;
                    if (((i&1))==1) insert_edge(s,get_id(i,j),1);
                    if (((i&1))==0) insert_edge(get_id(i,j)+n*m,t,1);
                }
                else if (a[i][j]=='B')
                {
                    sum_b++;
                    insert_edge(get_id(i,j),get_id(i,j)+n*m,1);
                    if (vaild(i-1,j)&&(a[i-1][j]=='W'))
                    {
                        if (((i&1))==0) insert_edge(get_id(i-1,j),get_id(i,j),1);
                        if (((i&1))==1) insert_edge(get_id(i,j)+n*m,get_id(i-1,j)+n*m,1);
                    }
                    if (vaild(i+1,j)&&(a[i+1][j]=='W'))
                    {
                        if (((i&1))==0) insert_edge(get_id(i+1,j),get_id(i,j),1);
                        if (((i&1))==1) insert_edge(get_id(i,j)+n*m,get_id(i+1,j)+n*m,1);
                    }
                    if (vaild(i,j-1)&&(a[i][j-1]=='W'))
                    {
                        if (((i&1))==1) insert_edge(get_id(i,j-1),get_id(i,j),1);
                        if (((i&1))==0) insert_edge(get_id(i,j)+n*m,get_id(i,j-1)+n*m,1);
                    }
                    if (vaild(i,j+1)&&(a[i][j+1]=='W'))
                    {
                        if (((i&1))==1) insert_edge(get_id(i,j+1),get_id(i,j),1);
                        if (((i&1))==0) insert_edge(get_id(i,j)+n*m,get_id(i,j+1)+n*m,1);
                    }
                }
            }
        }
        int ans=2*max_flow(s,t);
        if ((ans==sum_w)&&(ans==2*sum_b))
        {
            puts("YES");
        }
        else
        {
            puts("NO");
        }
    }
    return 0;
}