题目大意:

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

思路:一开始的暴力思路是对于每个串,若想使得它成为字典序最小的串,就找到它和任意其他串的从前向后第一个字母不同的位置,并添加限制:这个串的该位置字母的字典序小于其他串的该位置字母的字典序.这样若限制无环,我们就说这个串可以是字典序最小的.

然而这样建图花费的时间太长.

若将所有的串插入一颗Trie树,考虑对于每个串,其需要考虑的限制仅仅是从根节点到串的结尾所对应的节点的路径上的分岔.这样限制数最多为\(O(L*26)\),那么总的限制数最多为\(O(300000*26)\),就可以暴力建图并利用TarjanCheck了.

(为什么没想到Trie树..)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 30010
#define L 300010

int ch[L][26],cnt,isend[L];
char s[L];int begin[N],len[N];

int G[26][26];
inline void reset(){memset(G,0,sizeof G);}
inline void addedge(int a,int b){/*printf("%d %d\n",a,b);*/G[a][b]=1;}

int dfn[26],low[26],tclock,stk[26],top,num;bool instk[26];
void dfs(int x){
	dfn[x]=low[x]=++tclock;stk[++top]=x,instk[x]=1;
	for(int j=0;j<26;++j)if(G[x][j]){
		if(!dfn[j])dfs(j),low[x]=min(low[x],low[j]);
		else if(instk[j])low[x]=min(low[x],dfn[j]);
	}if(dfn[x]==low[x]){
		++num;
		while(1){int i=stk[top--];instk[i]=0;if(x==i)break;}
	}
}
inline bool judge(){
	memset(dfn,0,sizeof dfn);tclock=top=num=0;memset(instk,0,sizeof instk);
	for(int i=0;i<26;++i)if(!dfn[i])dfs(i);
	return num==26;
}

int ans[N],siz;
int main(){
	int n;cin>>n;
	register int i,j,k;
	int now=0;for(i=1;i<=n;++i)begin[i]=now,scanf("%s",s+now),len[i]=strlen(s+now),now+=len[i];
	int p,y;
	for(i=1;i<=n;++i){
		for(p=0,j=0;j<len[i];++j){if(!ch[p][y=s[begin[i]+j]-'a'])ch[p][y]=++cnt;p=ch[p][y];}
		isend[p]=i;
	}
	for(i=1;i<=n;++i){
		bool notok=0;
		for(reset(),p=0,j=0;j<len[i];p=ch[p][y],++j){
			if(isend[p]&&isend[p]!=i)notok=1;
			y=s[begin[i]+j]-'a';for(k=0;k<26;++k)if(k!=y&&ch[p][k])addedge(y,k);
		}
		if(!notok&&judge())ans[++siz]=i;
	}
	printf("%d\n",siz);
	//for(i=1;i<=siz;++i)printf("%d\n",ans[i]);
	for(i=1;i<=siz;++i){for(j=0;j<len[ans[i]];++j)putchar(s[begin[ans[i]]+j]);puts("");}
	return 0;
}