至今没看懂这深搜怎么写的……
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 inline int read(){ 10 #define num ch-'0' 11 char ch;bool flag=0;int res; 12 while(!isdigit(ch=getc())) 13 (ch=='-')&&(flag=true); 14 for(res=num;isdigit(ch=getc());res=res*10+num); 15 (flag)&&(res=-res); 16 #undef num 17 return res; 18 } 19 #define Nosolution ((n==19)?20:30) 20 const int N=1005; 21 int w[N][N]; 22 inline void add(int u,int v){ 23 w[u][++w[u][0]]=v; 24 w[v][++w[v][0]]=u; 25 } 26 int Brk[N],b[N],lca[N][N],d[N],vis[N],p[N],has[N]; 27 int s,t,n,dep,now; 28 queue<int> q; 29 void spfa(int s){ 30 memset(d,0x3f,sizeof(d)); 31 d[s]=0,q.push(s),vis[s]=1; 32 while(!q.empty()){ 33 int u=q.front();q.pop();vis[u]=0; 34 for(int i=1;i<=w[u][0];++i){ 35 int v=w[u][i]; 36 if(d[v]>d[u]+1){ 37 d[v]=d[u]+1,p[v]=u; 38 if(!vis[v]) vis[v]=1,q.push(v); 39 } 40 } 41 } 42 } 43 int cost=0; 44 bool dfs(int deep){ 45 if(b[t]==2) return true; 46 if(deep+lca[now][t]+cost>dep) return false; 47 for(int i=1;i<=Brk[0];++i){ 48 int u=Brk[i]; 49 for(int j=1;j<=w[u][0];++j){ 50 int v=w[u][j]; 51 if(!b[v]){ 52 Brk[i]=v; 53 if(u==now) now=v; 54 if(has[u]&&!has[v]&&b[u]!=2) --cost; 55 if(has[v]&&!has[u]&&b[u]!=2) ++cost; 56 swap(b[v],b[u]); 57 if(dfs(deep+1)) return true; 58 if(has[u]&&!has[v]&&b[v]!=2) ++cost; 59 if(has[v]&&!has[u]&&b[v]!=2) --cost; 60 if(now==v) now=u; 61 Brk[i]=u; 62 swap(b[v],b[u]); 63 } 64 } 65 } 66 return false; 67 } 68 int main(){ 69 //freopen("testdata.in","r",stdin); 70 n=read(),s=read(),t=read(); 71 now=s; 72 Brk[++Brk[0]]=s; 73 for(int i=0;i<n;++i){ 74 b[i]=read()^1; 75 if(b[i]) Brk[++Brk[0]]=i; 76 int s,v; 77 s=read(); 78 for(int j=0;j<s;++j){ 79 v=read(); 80 if(!lca[i][v]&&lca[v][i]){ 81 add(i,v); 82 } 83 lca[i][v]=1; 84 } 85 } 86 b[s]=2; 87 for(int i=0;i<n;++i){ 88 spfa(i); 89 for(int j=0;j<n;++j) lca[i][j]=d[j]; 90 if(i==s){ 91 int u=t; 92 while(u!=s){ 93 has[u]=1; 94 if(b[u]==1) ++cost; 95 u=p[u]; 96 } 97 has[s]=1; 98 } 99 } 100 for(dep=1;dep<=6;++dep) 101 if(dfs(0)) return printf("%d ",dep),0; 102 printf("%d ",Nosolution); 103 return 0; 104 }