UVA - 11604 General Sultan

对每两个字符串进行匹配然后连边=看程序应该能看懂

开始st没清零不停地爆oj

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define rep(j,k,l) for (int j=k;j<=l;++j)
#define M 25
#define N 110
#define P 250010

using namespace std;
int n,T,cnt,len[N],to[P][2],ne[P],st[N][M],used[N][M];
char s[N][M];
bool lych;

inline void add(int k1,int k2,int l1,int l2){
	
	to[++cnt][0]=l1;to[cnt][1]=l2;
	ne[cnt]=st[k1][k2];
	st[k1][k2]=cnt;
	
}

inline void init(){
	
	rep(i,1,n){
		
		scanf("%s%s",s[i]+1,s[i]+1);
		len[i]=strlen(s[i]+1);
		
	}
	cnt=0;
	memset(st,0,sizeof(st));
	rep(i,1,n) add(0,0,i,1);
	rep(k,1,n) rep(l,1,n) if (k!=l)
		rep(o,1,len[k]){
			
			int p=1;
			while (o+p-1<=len[k]&&p<=len[l]&&s[k][o+p-1]==s[l][p]) p++;
			if (o+p-1>len[k]){
				
				if (p>len[l]) add(k,o,n+1,0);
				else add(k,o,l,p);
				
			}else if (p>len[l]) add(k,o,k,o+p-1);
	
		}
	
}

inline void dfs(int k,int l){
	
	if (k==n+1){
		
		lych=1;
		return;
		
	}
	used[k][l]=T;
	for (int i=st[k][l];i;i=ne[i]){
		
		int o=to[i][0],p=to[i][1];
		if (used[o][p]!=T) dfs(o,p);
		if (lych) return;
		
	}
	
}

inline void work(){
	
	T++;
	lych=0;
	dfs(0,0);
	if (lych) printf("Case #%d: Ambiguous.\n",T);
	else printf("Case #%d: Not ambiguous.\n",T);
	
}

int main(){
	
	while (scanf("%d",&n)!=EOF&&n){
		
		init();
		work();
		
	}
	return 0;
	
}