本文主要是介绍hdu 3313 Key Vertex 那些AC的代码基本都是错的！，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
8 9 1 4 0 2 2 4 4 5 3 5 2 6 6 3 0 7 7 1 0 5这组数据，答案应该是2， 网上的题解都输出3 他们的搜索方法不对
先看他们错误算法的描述：“先找一条从s到t的任意路径，假如没有路的话，那么割点数为n，如果找到了一条路径的话，将这条路径上的点标记出来，首先明确一点，割点肯定不会再路径外的点上，因为去掉外面的点后，还是有刚刚那条路径的。所以现在就要看路径上的每个点是不是割点。只要把路径上的点去掉，然后从s进行bfs，路径上的点不能走，这样进行bfs的记录能探访到最远的在路径上的点为ans，假如ans等于t，那么只有两个割点s和t，如果bfs结束后ans不等于t，那么ans就是一个割点。因为去掉该点之后，无法走到之后的点了。然后从ans开始继续进行bfs直到访问到t为止。”
问题在于，bfs到的ans不一定是一个关键点！
假设我们对最短路径上的点根据距离起点的距离进行编号， 那么s就是0。 从s 搜索 到 ans，假设ans的编号是 A， 如果在路径上0到A之间有一个点能够bfs到一个点ans2，编号为B，且B > A, 那么 ans就不是一个关键点！
正确做法应该是0到A之间的点全都要bfs！ 正确代码如下：#include<stdio.h> #include<string.h> #include<ctype.h> #include<math.h> #include<string> #include<vector> #include<queue> #include<algorithm> using namespace std; void fre(){freopen("t.txt","r",stdin);} #define ls o<<1 #define rs o<<1|1 #define MS(x,y) memset(x,y,sizeof(x)) typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; const int INF = 0x3f3f3f3f; const int dir[4][2] = {1,0,0,1,-1,0,0,-1}; const int MAXN = 100010; const int MAXM = 300010; //输入挂 char IN; int NEG; inline void Int(int &x){NEG = 0;while(!isdigit(IN=getchar()))if(IN=='-')NEG = 1;x = IN-'0';while(isdigit(IN=getchar()))x = x*10+IN-'0';if(NEG)x = -x; } struct edge {int v,nxt; }e[MAXM]; int tot,head[MAXN]; void addedge(int u,int v) {e[tot] = (edge){v,head[u]}; head[u] = tot++; } int n,m,End; int dep[MAXN],pre[MAXN],Q[MAXN],path[MAXN],in[MAXN]; bool vis[MAXN]; bool bfs(int s,int t) {for(int i = 0; i < n; ++i) pre[i] = dep[i] = -1;int L = 0, R = 0;Q[R++] = s; dep[s] = 0;while(L < R){int u = Q[L++];for(int i = head[u]; i != -1; i = e[i].nxt){int v = e[i].v;if(dep[v] != -1) continue;pre[v] = u; dep[v] = dep[u] + 1;if(v == t) return 1;Q[R++] = v;}}return 0; } int bfs2(int s) {int L = 0, R = 0,MAX = 0;Q[R++] = s; vis[s] = 1;while(L < R){int u = Q[L++];for(int i = head[u]; i != -1; i = e[i].nxt){int v = e[i].v;if(in[v]){if(in[v] > MAX) MAX = in[v];continue;}if(vis[v]) continue;vis[v] = 1;Q[R++] = v;if(MAX == End) return MAX;}}return MAX; } int solve() {tot = 0; MS(head,-1);for(int i = 0; i < n; ++i) vis[i] = in[i] = 0;int u,v,s,t;while(m--){Int(u);Int(v);addedge(u,v);}Int(s); Int(t);if(!bfs(s,t)) return n;u = t; End = dep[t];while(u != -1) in[u] = End, path[End--] = u, u = pre[u] ;End = dep[t];int ans = 0,L = 0, R = 0;while(R != End){if(L == R) ans++;R = max(R,bfs2(path[L]));L++;}return ans+1; } int main() {while(~scanf("%d%d",&n,&m))printf("%d\n",solve()); }
这篇关于hdu 3313 Key Vertex 那些AC的代码基本都是错的！的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
