思路:

本题的模型转换十分巧妙:

仅考虑空格移动,注意到空格移动的路径事实上是黑白相间,且不自交的路径.

这样我们黑白染色变成二分图,转化为二分图上的博弈问题.

显然的性质是从一个点出发先手必胜当且仅当这个点是二分图最大匹配的必须点.

若这个点没有匹配点,先手必败;否则将这个点的匹配点的匹配点设为0,删除这个点,并从这个点的匹配点开始增广.若能够增广,显然这个点不是必须点.

这样只需增广\(O(K)\)次,时间复杂度\(O(KN^4)\).

(另外本沙茶终于明白匈牙利算法是怎回事了...)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
 
#define N 41
int ano[N*N];
bool changed[N*N];
 
int head[N*N],next[N*N<<2],end[N*N<<2];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
}
inline void make(int a,int b){
    addedge(a,b);
    addedge(b,a);
}
 
bool del[N*N];
inline bool dfs(int x){
    if(del[x])return 0;
    for(int j=head[x];j;j=next[j]){
        if(!changed[end[j]]&&!del[end[j]]){
            changed[end[j]]=1;
            if(!ano[end[j]]||dfs(ano[end[j]])){
                ano[x]=end[j],ano[end[j]]=x;
                return 1;
            }
        }
    }
    return 0;
}
 
char s[N];
int map[N][N],lab[N][N];
inline int hash(char c){
    if(c=='X')return 0;
    if(c=='O')return 1;
    return 2;
}
 
inline int getdis(int x,int y){
    return x>y?x-y:y-x;
}
 
#define Q 2010
bool win[Q];
 
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
     
    register int i,j;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)map[i][j]=hash(s[j]);
    }
     
    int x,y;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(map[i][j]==2)
                x=i,y=j;
     
    int id=0;
    map[x][y]=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if((((getdis(i,x)+getdis(j,y))%2)^map[i][j])==0)
                lab[i][j]=++id;
     
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)if(lab[i][j]){
            if(lab[i-1][j])addedge(lab[i][j],lab[i-1][j]);
            if(lab[i+1][j])addedge(lab[i][j],lab[i+1][j]);
            if(lab[i][j-1])addedge(lab[i][j],lab[i][j-1]);
            if(lab[i][j+1])addedge(lab[i][j],lab[i][j+1]);
        }
     
    for(i=1;i<=id;++i)
        if(!ano[i])memset(changed,0,sizeof changed),dfs(i);
 
    int steps;
    scanf("%d",&steps);
    steps<<=1;
    for(i=1;i<=steps;++i){
        if(ano[lab[x][y]]){
            int t=ano[lab[x][y]];
            ano[lab[x][y]]=ano[t]=0;
            del[lab[x][y]]=1;
            memset(changed,0,sizeof changed);
            win[i]=!dfs(t);
        }
        else{
            del[lab[x][y]]=1;
            win[i]=0;
        }
        scanf("%d%d",&x,&y);
    }
     
    int re=0;
    for(i=1;i<=steps;i+=2){
        if(win[i]&&win[i+1])++re;
    }
    printf("%d\n",re);
    for(i=1;i<=steps;i+=2){
        if(win[i]&&win[i+1])
            printf("%d\n",(i+1)>>1);
    }
    return 0;
}

思路:

首先将图黑白二染色变成二分图.

然后求出一组最大匹配.

如果某个点不在匹配中,那么先手选择这个点.

那么后手只能走向一个匹配点(否则就不是最大匹配了).于是先手就可以沿着匹配边走回来.

那么此时如果后手还能走的话,就必定走到一个匹配点上.(否则就存在增广路了).于是先手又沿着匹配边走回来.

最后总是后手无路可走.因此先手必胜.

因此如果某个点不是最大匹配的必须点.就可以选择这个点.

如何找出这个呢?

在残量网络上,从\(S\)出发能够遍历到的左端的点,以及从\(T\)出发能够反向遍历到的右端的点.

证明的话,就是如果能够遍历到,就证明可以被换掉,而使得匹配数不减少.(稍微脑补一下)

(注意总点数要开2W,我不知道为什么)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF ~0U>>1
struct Solver{
    static const int V=20010;
    static const int E=V<<2;
    int head[V],next[E],end[E],flow[E],ind;
    int gap[V],d[V],stk[V],top,cur[V];
    inline void reset(){
        ind=top=0,memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;
        end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
    }
    inline void make(int a,int b,int f){
        //printf("%d %d %d\n",a,b,f);
        addedge(a,b,f),addedge(b,a,0);
    }
    inline void bfs(int T){
        static int q[V];
        int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
                ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T){
        int re=0,ins,Min,i,u=S;
        bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<T-S+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i;
                for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
                find=1,ins=j;break;
            }
            if(find){
                stk[top++]=cur[u]=ins,u=end[ins];
            }
            else{
                Min=T-S+1;
                for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
                    cur[u]=j,Min=d[end[j]];
                if(!--gap[d[u]])break;
                ++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }
        return re;
    }
}Stg;
 
#define N 110
char s[N];
int lab[N][N],x[N*N],y[N*N];
 
int res[N*N],nums;
 
bool vis[N*N];
inline void bfs(int S,bool rev){
    static int q[N*N];
    int fr=0,ta=0;
    memset(vis,0,sizeof vis),vis[S]=1,q[ta++]=S;
    while(fr^ta){
        int i=q[fr++];
        for(int j=Stg.head[i];j!=-1;j=Stg.next[j])if(Stg.flow[j^rev]&&!vis[Stg.end[j]])
            vis[Stg.end[j]]=1,q[ta++]=Stg.end[j];
    }
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);
    register int i,j;
    int cnt=0;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)if(s[j]!='#')lab[i][j]=++cnt,x[cnt]=i,y[cnt]=j;
    }
     
    int S=0,T=cnt+1,num0=0,num1=0;
    Stg.reset();
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]){
        if((i+j)&1){
            ++num1;
            Stg.make(S,lab[i][j],1);
            if(lab[i-1][j])Stg.make(lab[i][j],lab[i-1][j],INF);
            if(lab[i+1][j])Stg.make(lab[i][j],lab[i+1][j],INF);
            if(lab[i][j-1])Stg.make(lab[i][j],lab[i][j-1],INF);
            if(lab[i][j+1])Stg.make(lab[i][j],lab[i][j+1],INF);
        }
        else
            ++num0,Stg.make(lab[i][j],T,1);
    }
     
    if(num0==0&&num1==0){
        puts("LOSE");
        return 0;
    }
     
    int re=Stg.Maxflow(S,T);
     
    /*for(i=S;i<=T;++i)for(j=Stg.head[i];j!=-1;j=Stg.next[j])
        printf("%d %d %d\n",i,Stg.end[j],Stg.flow[j]);*/
    if(num0==num1&&re==num0){
        puts("LOSE");
        return 0;
    }
    puts("WIN");
     
    bfs(S,0);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)&1)&&vis[lab[i][j]])res[++nums]=lab[i][j];
    bfs(T,1);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)%2==0)&&vis[lab[i][j]])res[++nums]=lab[i][j];
    sort(res+1,res+nums+1);
     
    for(i=1;i<=nums;++i){
        printf("%d %d\n",x[res[i]],y[res[i]]);
    }
     
    return 0;
}

思路:

首先是一个DAG.

然后,你要选出最多的点,使得任意两个点之间不能有到达关系.

考虑将拓扑图划分为若干条点不相交路径,那么所有的结束点之间都是不能到达的.

那么我们就要求出DAG的最小路径覆盖.

然而事实上由于是DAG,路径的点是可以相交的.于是我们通过拆点转化为一般的点不相交最小路径覆盖.

考虑给每一个点找一个入点,那么每出现一个匹配,路径的数目就会减少1.

于是利用总点数减去最大匹配即可.

#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>

#define INF 0x3f3f3f3f

#define N 210
struct MaxflowSolver{
	static const int V=N<<1;
	static const int E=N*N<<1;
	int head[V],next[E],end[E],flow[E],ind;
	int d[V],gap[V],stk[V],top,cur[V];
	inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
	inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
	inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
	inline void bfs(int T){
		static int q[V];int fr=0,ta=0;
		memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
		while(fr^ta){
			int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
		}
	}
	inline int Maxflow(int S,int T,int cnt){
		int res=0,u=S,i,Min,ins;bfs(T),memcpy(cur,head,sizeof cur);
		while(d[S]<cnt){
			if(u==T){
				for(Min=INF,i=0;i<top;++i)if(flow[stk[i]]<Min)Min=flow[stk[i]],ins=i;
				for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
				u=end[stk[top=ins]^1];
			}
			if(u!=T&&!gap[d[u]-1])break;
			bool find=0;
			for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
			if(find)cur[u]=stk[top++]=ins,u=end[ins];
			else{
				Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
				if(!--gap[d[u]])break;++gap[d[u]=Min+1];
				if(u!=S)u=end[stk[--top]^1];
			}
		}return res;
	}
}SteinsGate;

int head[N],next[N*N],end[N*N];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}

int seq[N],cnt;bool vis[N];
void dfs(int x){
	vis[x]=1,seq[++cnt]=x;
	for(int j=head[x];j;j=next[j])if(!vis[end[j]])dfs(end[j]);
}
int main(){
	int n,m;scanf("%d%d",&n,&m);register int i,j;
	int a,b;while(m--)scanf("%d%d",&a,&b),addedge(a,b);

	SteinsGate.reset();
	for(i=1;i<=n;++i){
		memset(vis,0,sizeof vis);
		cnt=0,dfs(i);
		for(j=1;j<=cnt;++j)if(seq[j]!=i)SteinsGate.make(i,n+seq[j],1);
	}

	int S=0,T=2*n+1;
	for(i=1;i<=n;++i)SteinsGate.make(0,i,1);
	for(i=1;i<=n;++i)SteinsGate.make(n+i,T,1);

	printf("%d",n-SteinsGate.Maxflow(S,T,2*n+2));

#ifndef ONLINE_JUDGE
	system("pause");
#endif
	return 0;
}

题目大意:

给定一个二分图以及一组已知的完备匹配,要求对于每个\(X\)集合中的点确定这个点与哪些个\(Y\)集合中的点匹配时,依然能够存在完备匹配.

思路:

考虑完备匹配中,\(X_i->Y_i,X_j->Y_j\),那么如果现在想要\(X_i->Y_j\),那么就要保证这样做之后从\(X_j\)出发存在增广路,否则就不能形成完备匹配.

那么这条增广路的终点显然应该是\(Y_i\),也即存在必定存在路径\(X_j->Y_i\).

我们考虑将之前给出的完备匹配的反向边连回去:即若存在匹配\(X_i->Y_i\),则连接有向边\(Y_i->X_i\).

那么我们考虑有路径\(X_j->Y_i->X_i->Y_j->X_j\),就是说形成了一个环,那么这些点必定在一个强连通分量中!

考虑与某个点\(X_i\)在一个强连通分量一些\(Y\)集合的点\(Y_k\),若存在边\(X_i->Y_k\),那么就是说\(Y_k\)要么是\(X_i\)原来的完备匹配,要么可以通过交换重新找到增广路得到完备匹配.

因此我们求一次SCC就解决了这道题目.

#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>

#define N 2010

namespace Fio{
	inline int getc(){
#ifdef ONLINE_JUDGE
		static const int L=1<<15;
#else
		static const int L=1<<1;
#endif
		static char buf[L],*S=buf,*T=buf;
		if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
		return*S++;
	}
	inline bool digit(int c){return c>='0'&&c<='9';}
	template<typename T>inline void Get(T&x){
		int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
	}
	char buf[5000000],*o=buf;
	inline void putc(char c){*o++=c;}
	template<typename T>inline void print(T x){
		static int stk[100];int top=0;
		for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++='0'+stk[i];
	}
	inline void Final(){fwrite(buf,1,o-buf,stdout);}
}

int head[4010],next[2010*2010],end[2010*2010];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}

int G[2010][2010],dfn[4010],low[4010],tclock,stk[4010],bel[4010],cnt,top;bool instk[4010];

void dfs(int x){
	dfn[x]=low[x]=++tclock;stk[++top]=x,instk[x]=1;
	for(int j=head[x];j;j=next[j]){
		if(!dfn[end[j]])dfs(end[j]),low[x]=std::min(low[x],low[end[j]]);
		else if(instk[end[j]])low[x]=std::min(low[x],dfn[end[j]]);
	}
	if(dfn[x]==low[x]){
		++cnt;
		while(1){
			int i=stk[top--];instk[i]=0;
			bel[i]=cnt;
			if(i==x)break;
		}
	}
}

int seq[2010],id;

int main(){
	int n;Fio::Get(n);register int i,j;
	int t,x;for(i=1;i<=n;++i){Fio::Get(t);while(t--)Fio::Get(x),G[i][x]=1,addedge(i,n+x);}

	for(i=1;i<=n;++i)Fio::Get(x),addedge(n+x,i);

	for(i=1;i<=2*n;++i)if(!dfn[i])dfs(i);

	for(i=1;i<=n;++i){
		for(id=0,j=1;j<=n;++j)if(bel[i]==bel[n+j]&&G[i][j])seq[++id]=j;
		Fio::print(id);
		for(j=1;j<=id;++j)Fio::putc(' '),Fio::print(seq[j]);
		Fio::putc('\n');
		//printf("%d",id);
		//for(j=1;j<=id;++j)printf(" %d",seq[j]);
		//puts("");
	}

	Fio::Final();

#ifndef ONLINE_JUDGE
	system("pause");
#endif
	return 0;
}