又犯了个SB错误。。。
这道题算是一道比较神的题了，思路特别难找。下面给出题面：
第一问其实很简单，建立一个bool数组，从0开始枚举所有点，暂时将该点标为true（即不需要进行搜索），然后进行dfs，如果无法到达终点，那么这个点一定是必须要经过的点。
第二问看似很难，实际上确实特别难，但从题意中我们用显而易见法可以证明，凡是中间路口都是不可避免的路口，但不可避免的路口不一定是中间路口。
但是在什么情况下的不可避免的路口不是中间路口呢？
从问题二的解释中我们可以得到，如果从某一不可避免的路口出发，到达终点的过程中存在某一路口的某一条路通往该不可避免的路口之前的路口，那么这个不可避免的路口就不是中间路口。
这样的话我们可以设计三个dfs方案，第一个dfs方案搜索所有不可避免的路口，第二个dfs方案搜索从起点到某个不可避免路口中可经过的所有点，并将所有点标记为真，第三个dfs方案查找从某个不可避免的路口出发是否有路能通往该点之前的路口，在每通过第一个方案找到一个不可避免的路口时对该路口进行第二个与第三个dfs，如果经过了该点之前的路口，这个路口一定不是中间路口。
通过这样的方法，我们就能将所有的不可避免的路口与中间路口记录下来了。代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int a[60][60],nummid=0,numcross=0,st,en,sum,arca[60][60],np; 6 bool cross[60],mid[60],f[60],flag,fc[60][60]; 7 void init() 8 { 9 int inn[60],outt[60]; 10 memset(inn,0,sizeof(inn)); 11 memset(outt,0,sizeof(outt)); 12 int j,i=-1; 13 scanf("%d",&j); 14 while (j!=-1) 15 { 16 i++; 17 while(j!=-2) 18 { 19 a[i][j]=1; 20 arca[j][i]=1; 21 arca[i][j]=1; 22 outt[i]++; inn[j]++; 23 scanf("%d",&j); 24 } 25 if (outt[i]==0) en=i; 26 scanf("%d",&j); 27 for (int j=0;j<=i;j++) 28 if (inn[j]==0) st=j; 29 } 30 sum=i; 31 //printf("%d %d\n",inn[st],outt[en]); 32 //printf("%d %d\n",st,en); 33 } 34 35 void dfs(int p) 36 { 37 if (p==en) 38 { 39 flag=true; 40 return; 41 } 42 for (int i=0;i<=sum;i++) 43 if (!f[i]&&a[p][i]==1) 44 { 45 f[i]=true; 46 dfs(i); 47 if (flag) 48 return; 49 } 50 } 51 52 void dfs1(int p) 53 { 54 for (int i=0;i<=sum;i++) 55 if (!f[i]&&a[p][i]==1) 56 { 57 f[i]=true; 58 dfs1(i); 59 fc[np][i]=true; 60 } 61 } 62 63 void dfs2(int p) 64 { 65 if (fc[np][p]) 66 { 67 flag=false; 68 return; 69 } 70 for (int i=0;i<=sum;i++) 71 if (!f[i]&&a[p][i]==1) 72 { 73 f[i]=true; 74 dfs2(i); 75 if (!flag) 76 return; 77 } 78 } 79 int main() 80 { 81 //freopen("add.in","r",stdin); 82 //freopen("add.out","w",stdout); 83 memset(arca,0,sizeof(arca)); 84 memset(cross,false,sizeof(cross)); 85 memset(mid,false,sizeof(mid)); 86 memset(a,0,sizeof(a)); 87 memset(f,true,sizeof(f)); 88 memset(fc,false,sizeof(fc)); 89 init(); 90 for (int i=0;i<=sum;i++) 91 { 92 np=i; 93 fc[np][np]=true; 94 int num=0; 95 if (i==st||i==en) 96 continue; 97 memset(f,false,sizeof(f)); 98 f[i]=true; 99 flag=false; 100 dfs(st); 101 if (!flag) 102 { 103 numcross++; 104 cross[i]=true; 105 flag=true; 106 memset(f,false,sizeof(f)); 107 f[i]=true; 108 dfs1(i); 109 memset(f,false,sizeof(f)); 110 f[i]=true; 111 dfs2(st); 112 if (flag) 113 { 114 nummid++; 115 mid[i]=true; 116 } 117 } 118 } 119 printf("%d ",numcross); 120 for (int i=0;i<=sum;i++) 121 if (cross[i]) 122 printf("%d ",i); 123 printf("\n"); 124 printf("%d ",nummid); 125 for (int i=0; i<=sum; i++) 126 if (mid[i]) 127 printf("%d ",i); 128 printf("\n"); 129 return 0; 130 }
原文：http://www.cnblogs.com/hinanawitenshi/p/6539511.html
