题解 P3858 【[TJOI2008]贪吃蛇】

GNAQ · 2019-01-22 20:26:10 · 题解

拿下一血，补个题解吧。

二分图 × 博弈

这题实际上是 P4055 [JSOI2009]游戏 ←这货的三维 弱化不用求方案但是多组数据很恶心 版

然而就算是三维，照样可以黑白染色然后套二分图博弈模型。因为走法都是某种颜色的格子到异色的格子，所以二维的所有二分图博弈结论全部可以照搬过来。

然后就照着那个题做就行了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
#define ll long long
#define fst first
#define snd second
using namespace std;

int R,C,H,id[110][110][110],ids; bool ans;

int dx[6]={0,-1,0,1,0,0},dy[6]={-1,0,1,0,0,0},dz[6]={0,0,0,0,1,-1};

template<typename int_t>
void readx(int_t& x)
{
    x=0; int_t k=1; char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

// Bipartite graph matching
struct ed
{
    int pre,to;
}edge[4010];
int at,ptr[110];
vector<int> sts;
int visV[110],mat[110];

void Is(int fx,int tx)
{
    at++;
    edge[at].pre=ptr[fx];
    edge[at].to=tx;
    ptr[fx]=at;
    at++;
    edge[at].pre=ptr[tx];
    edge[at].to=fx;
    ptr[tx]=at;
}

bool Hungary(int now,int src)
{
    for (int v=ptr[now];v;v=edge[v].pre) if (visV[edge[v].to]!=src)
    {
        visV[edge[v].to]=src;
        if (!mat[edge[v].to] || Hungary(mat[edge[v].to],src)) { mat[edge[v].to]=now; return true; }
    }
    return false;
}

// Build Graph
struct _Node
{
    int x,y,z;
    _Node() {}
    _Node(int ix,int iy,int iz) { x=ix; y=iy; z=iz; }
};
queue<_Node>que; _Node cac;
bool vis[110];
void BFS_Build(_Node str)
{
    // Clear Graph
    at=1; memset(ptr,0,sizeof ptr); sts.clear();
    memset(visV,0,sizeof visV); memset(mat,0,sizeof mat);

    que.push(str); vis[id[str.x][str.y][str.z]]=1;
    while (!que.empty())
    {
        cac=que.front(); que.pop(); 
        int nx=cac.x,ny=cac.y,nz=cac.z,nid=id[nx][ny][nz];
        sts.push_back(nid);

        for (int w=0;w<6;w++) 
        {
            int tid=id[nx+dx[w]][ny+dy[w]][nz+dz[w]];
            if (!vis[tid]) // vis[0]=1!!
            {
                vis[tid]=1;
                que.push(_Node(nx+dx[w],ny+dy[w],nz+dz[w]));
            }
            if (tid && (nx+ny+nz)%2) Is(nid,tid);
        }
    }
}

void Solve()
{
    ids=0; ans=0; memset(vis,0,sizeof vis); vis[0]=1;
    memset(id,0,sizeof id);

    // read
    readx(H); readx(R); readx(C); char ch=0;
    for (int k=1;k<=H;k++)
        for (int i=1;i<=R;i++)
            for (int j=1;j<=C;j++)
            {
                ch=0; while (ch!='.' && ch!='X') ch=getchar();
                if (ch=='.') id[i][j][k]=++ids;
            }

    for (int i=1;i<=R;i++)
        for (int j=1;j<=C;j++)
            for (int k=1;k<=H;k++) if (id[i][j][k] && !vis[id[i][j][k]])
            {
                // Make bipartite graph
                BFS_Build(_Node(i,j,k)); 
                for (unsigned u=0;u<sts.size();u++) 
                    if (!Hungary(sts[u],sts[u])) ans|=1;
            }
    printf(ans?"yes\n":"no\n");
}

int main()
{
    int T; readx(T);
    while (T--)
    {
        Solve();
    }
}