BZOJ:1443: [JSOI2009]游戏Game

时间：2023-03-08 16:59:31

原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1443

反正不看题解我是完全想不出系列……

先把棋盘黑白染色，也就是同一对角线上颜色相同，使得一个格子上下左右都不同色。

然后我们会发现，某一个人所走的全部格子颜色都是相同的。

把黑白格子当作点提取出来，放在两边，就变成了二分图，游戏的全过程变得像匈牙利算法的增广。

这提示我们也许跟二分图匹配有关。

如果一个点必定在最大匹配中，而一开始棋子放在了这里小YY只要沿着匹配边走小AA就gg了。

注意这里说的是必定在最大匹配中，所以并不用担心出现走到某个非匹配点后小YY无路可走的情形，此时可以通过伪增广保持最大匹配数不变而使起点不在匹配点中。BZOJ:1443: [JSOI2009]游戏Game

对于匈牙利算法，可以通过类似的伪增广找出所有不一定在最大匹配中的点。

对于网络流，未被割掉与源汇相邻的边的点肯定是答案，至于其他可以是答案的点，可以通过走反向边（与匈牙利类似的交错路径）来实现到达汇点或从源点出发可达。也就是在残余网络中源点可达且在二分图靠近源点一侧的点，可到达汇点且在二分图靠近汇点一侧的点（没这俩限制就gg了）都是答案点。（注意建图时建单向边，即反向边初始流量为0）

#include<cstdio>

#include<algorithm>

#define MN 110001

using namespace std;

int read_p,read_ca;

inline int read(){

    read_p=;read_ca=getchar();

    while(read_ca<''||read_ca>'') read_ca=getchar();

    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p;

}

const int fx[]={,-,,},fy[]={,,,-};

struct na{int y,f,ne;}b[MN];

int n,m,l[MN],be[][],nm=,S,T,num=,d[MN],g[MN],c[MN],mmh=;

bool bo[MN],O_O[MN];

char s[][];

inline void add(int x,int y,int f){b[++num].y=y;b[num].f=f;b[num].ne=l[x];l[x]=num;}

inline void in(int x,int y,int f){add(x,y,f);add(y,x,);}

int sap(int x,int f){

    if (x==T) return f;

    int h=,q;

    for (int i=d[x];i;i=b[i].ne)

    if (b[i].f&&g[x]==g[b[i].y]+){

        q=sap(b[i].y,min(f-h,b[i].f));

        b[i].f-=q;b[i^].f+=q;h+=q;d[x]=l[x];

        if (h==f) return h;

        if (g[S]==nm) return h;

    }

    if (!--c[g[x]]) g[S]=nm;++c[++g[x]];d[x]=l[x];

    return h;

}

void dfs(int x,bool B){

    if (bo[x]) return;

    bo[x]=;O_O[x]^=B;

    for (int i=l[x];i;i=b[i].ne)

    if (b[i].f==B) dfs(b[i].y,B);

}

int main(){

    register int i,j,k;

    n=read();m=read();

    for (i=;i<=n;i++) scanf("%s",s[i]+);

    for (i=;i<=n;i++)

    for (j=;j<=m;j++) if (s[i][j]=='.') be[i][j]=++nm;

    S=++nm;T=++nm;

    for (i=;i<=n;i++)

    for (j=;j<=m;j++)

    if (s[i][j]=='.')

    for (k=;k<;k++)

    if (s[i+fx[k]][j+fy[k]]=='.')

    if ((i+j)&) in(be[i+fx[k]][j+fy[k]],be[i][j],);else in(be[i][j],be[i+fx[k]][j+fy[k]],);

    for (i=;i<=n;i++)

    for (j=;j<=m;j++)

    if (s[i][j]=='.') if (mmh++,O_O[be[i][j]]=((i+j)&)) in(be[i][j],T,);else in(S,be[i][j],);

    for (;g[S]<nm;mmh-=*sap(S,1e9));

    if (!mmh) return puts("LOSE"),;

    puts("WIN");

    dfs(S,);dfs(T,);

    for (i=;i<=n;i++)

    for (j=;j<=m;j++)

    if (s[i][j]=='.'&&bo[be[i][j]]&&O_O[be[i][j]]) printf("%d %d\n",i,j);

}

相关文章