POJ1904 King's Quest 二分图+强连通分量

题目大意:

给定一个二分图以及一组已知的完备匹配,要求对于每个\(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;
}