Mn Zn刚学二分图博弈,全WA求助
查看原帖
Mn Zn刚学二分图博弈,全WA求助
762019
yushanxuanfeng楼主2023/5/20 16:17
#include<bits/stdc++.h>
#define sb 1919810
#define N 100005
using namespace std;
int n,m,s,t,ans,cnt,p[N],h[N],dis[N];
struct E{int v,w,nex;}e[N];
void add(int u,int v,int w){
    e[cnt].v=v,e[cnt].w=w,e[cnt].nex=h[u];
    h[u]=cnt++;
    e[cnt].v=u,e[cnt].w=0,e[cnt].nex=h[v];
    h[v]=cnt++;
    // cout<<"                "<<u<<" "<<v<<endl;
}
int bfs(){
    for(int i=s;i<=t;i++) dis[i]=sb;
    dis[s]=0,p[0]=s;
    int l=0,r=1;
    while(l!=r){
        int u=p[l++];
        for(int i=h[u];i!=-1;i=e[i].nex){
            int v=e[i].v;
            if(dis[v]==sb&&e[i].w>0){
                p[r++]=v,dis[v]=dis[u]+1;
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dfs(int u,int sum){
    if(u==t) return sum;
    int k,res=0;
    for(int i=h[u];i!=-1&&sum>0;i=e[i].nex){
        int v=e[i].v;
        if(dis[v]==dis[u]+1&&e[i].w>0){
            k=dfs(v,min(sum,e[i].w));
            if(k==0) dis[v]=sb;
            sum-=k,res+=k,e[i].w-=k,e[i^1].w+=k;
        }
    }
    return res;
}
vector<int>d[N];
int tot,top,cntt,dfn[N],low[N],scc[N],stk[N],instk[N];
void tarjan(int x){
    dfn[x]=low[x]=++tot;
    stk[++top]=x,instk[x]=1;
    for(int y:d[x]){
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        int y;
        cntt++;
        while(y!=x){
            y=stk[top--],instk[y]=0;
            scc[y]=cntt;
        }
    }
}
int a[105][105],g[N];
int suan(int i,int j){return i*m-m+j;}
int main(){
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    string str;
    s=0,t=n*m+1;
    for(int i=1;i<=n;i++){
        cin>>str;
        for(int j=1;j<=m;j++){
            if(str[j-1]=='.') a[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!a[i][j]) continue;
            if((i+j)%2) add(s,suan(i,j),1);
            else{
                add(suan(i,j),t,1);
                if(a[i-1][j]) g[suan(i,j)]++,g[suan(i-1,j)]++,add(suan(i-1,j),suan(i,j),1);
                if(a[i+1][j]) g[suan(i,j)]++,g[suan(i+1,j)]++,add(suan(i+1,j),suan(i,j),1);
                if(a[i][j-1]) g[suan(i,j)]++,g[suan(i,j-1)]++,add(suan(i,j-1),suan(i,j),1);
                if(a[i][j+1]) g[suan(i,j)]++,g[suan(i,j+1)]++,add(suan(i,j+1),suan(i,j),1); 
            }
        }
    }
    while(bfs()) ans+=dfs(s,sb);
    for(int u=s;u<=t;u++){
        for(int i=h[u];i!=-1;i=e[i].nex){
            int v=e[i].v;
            if(e[i].w){
                d[u].push_back(v);
                // cout<<u<<" "<<v<<endl;
            } 
        }
    }
    for(int i=s;i<=t;i++) if(!dfn[i]) tarjan(i);
    // for(int i=s;i<=t;i++) cout<<"scc["<<i<<"]="<<scc[i]<<endl;
    int flag=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!a[i][j]) continue;
            if((i+j)%2){
                if(scc[suan(i,j)]==scc[s]||!g[suan(i,j)]){
                    if(!flag){ flag=1;printf("WIN\n"); }
                    printf("%d %d\n",i,j);
                }
            }
            else{
                if(scc[suan(i,j)]==scc[t]||!g[suan(i,j)]){
                    if(!flag){ flag=1;printf("WIN\n"); }
                    printf("%d %d\n",i,j);
                }
            } 
        }
    }
    if(!flag) printf("LOSE");
}
2023/5/20 16:17
加载中...