Codeforces 120 H. Brevity is Soul of Wit

問題

文字列の、「4文字以下の（必ずしも連続しない）部分文字列」をその文字の略称にできるとする。

与えられたn個の文字列の略称を、重複なく定められるかどうかを判定せよ。
重複なく定められる場合、その略称をどれか一組出力し、
そうでない場合-1を出力せよ。

制約条件

n≦200

方針

文字列および、略称を頂点として、対応しうる略称に辺を引いたグラフを考える。
これは二部グラフであり、重複なく略称が定められるかは、このグラフが大きさnのマッチングを持つことに同値である。

したがって、グラフを作成し、二部グラフの最大マッチングを求めればよい。

グラフをあんまりナイーブに作成するとTLEになった。
どの文字列の略称にもなりえない文字列は生成しないようにし、
略称が対応するかを、使われている文字種で枝刈りしたら通った。

ソースコード

int n,m;
string in[200];
vi g[500000];
vector<string> list;
int p[500000],use[200];
bool v[500000];

bool match(int s){
	if(s<0)return 1;
	rep(i,g[s].size())if(!v[g[s][i]]){
		v[g[s][i]]=1;
		if(match(p[g[s][i]]))return p[g[s][i]]=s, p[s]=g[s][i], 1;
	}
	return 0;
}
bool ok(string &a,string &b){
	int n=a.size(), m=b.size();
	for(int i=0,j=0;i<n;i++){
		if(a[i]==b[j])if(++j>=m)return 1;
	}
	return 0;
}
void gen(string s,int bit){
	if(!s.empty()){
		bool any=0;
		rep(i,n)if((~use[i]&bit)==0&&ok(in[i],s)){
			any=1;
			g[i].pb(list.size()+n);
			g[list.size()+n].pb(i);
		}
		if(any)list.pb(s);
		else return;
	}
	if(s.size()<4)for(char c='a';c<='z';c++){
		string t=s+c;
		gen(t,bit|1<<c-'a');
	}
}

void run()
{
	cin>>n;
	rep(i,n){
		cin>>in[i];
		use[i]=0;
		rep(j,in[i].size())use[i]|=1<<in[i][j]-'a';
	}
	list.clear();
	gen("",0);
	m=list.size();
	
	int cnt=0;
	memset(p,-1,sizeof(p));
	rep(i,n){
		rep(j,n+m)v[j]=0;
		if(p[i]<0)
			if(match(i))cnt++;
	}
	if(cnt<n)cout<<-1<<endl;
	else rep(i,n)cout<<list[p[i]-n]<<endl;
}