題意:
? ? ?給你一個有向圖,然后給你起點和終點,問你從起點到終點有多少個關鍵點,如果當前的這個點刪除了就無法從起點到終點,那么這個點就是一個關鍵點..


思路:
? ? ?(1)有兩種做法,我用的是最大流的,另一種是先跑最短路然后搜索,先說最大流,最大流的很容易理解,首先我們拆點建圖,每個點拆成兩個點,限流是1,然后起點和終點的限流是2,點于點之間是INF,跑一遍最大流,如果流量是0,說明不連接,那么所有的點都是關鍵點,輸出n,如果流量是2那么說明最小割是2,也就是說無論你把那個點刪除都不影響連通性,所以只有起點和終點是關鍵點,如果流量是1,那也就是說在路途中可能存在關鍵點,那么我們就

用暴力搜索的方式去找這些關鍵點,對于搜索這塊我自己卡了兩天了,今天才弄明白,首先我們定義跑完最大流后流量為0的邊為關鍵邊,首先第一個點一定是關鍵點,我們一個一個找,我的理解是 從當前的這個關鍵點出發,通過非關鍵邊搜索,第一個搜索不到的點一定是關鍵點,這里的搜索不到的點指的是我們比如當前邊u,v,他沿著非關鍵邊無法從u走到v,但是沿著關鍵邊可以走到,那么v就是第一個搜不到的點,v一定是關鍵點,跑完最大流后,流量0(正向)的是關鍵路徑上的點,非0的是非關鍵路徑上的點,我們每次從當前的關鍵點出發,沿著流量非0的跑,把這次跑到的點全記錄下來,mark上,然后枚舉每一個搜到的點相鄰的點,如果是流量0,那么這個就是第一個到達不了的點,那么他一定是關鍵點,這屆break,以這個點為起點在接著搜索,就這樣一直找到T為止.還有為什么上面有兩條邊是2而不是別的,是為了縮短時間,2最多兩次,我們是為了找到答案是0,1,還是其他,2.3.4..都是其他,都是只存在兩個關鍵點的,所以我們要節省時間,流量2,如果弄大了答案肯定對,但會TLE...

最大流已知當前點找下一個關鍵點的搜索過程,紅色是搜索路徑,當前點a,下一個關鍵點是c,
則如圖:

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<stdio.h> #include<string.h> #include<queue>#define N_node 200000 + 20 #define N_edge 600000 + 60 #define INF 1000000000 using namespace std;typedef struct {int to ,cost ,next; }STAR;typedef struct {int x ,t; }DEP;STAR E[N_edge]; DEP xin ,tou; int list[N_node] ,tot; int deep[N_node] ,list2[N_node]; int mark[N_node] ,num[N_node] ,tt;void add(int a, int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot;E[++tot].to = a;E[tot].cost = 0;E[tot].next = list[b];list[b] = tot; }int minn(int x ,int y) {return x < y ? x : y; }bool BFS(int s ,int t ,int n) {memset(deep ,255 ,sizeof(deep));deep[s] = 0;xin.x = s;xin.t = 0;queue<DEP>q;q.push(xin);while(!q.empty()){tou = q.front();q.pop();for(int k = list[tou.x] ;k ;k = E[k].next){xin.x = E[k].to;xin.t = tou.t + 1;if(deep[xin.x] != -1 || !E[k].cost)continue;deep[xin.x] = xin.t;q.push(xin);}}for(int i = 0 ;i <= n ;i ++)list2[i] = list[i];return deep[t] != -1; }int DFS_FLOW(int s ,int t ,int flow) {if(s == t) return flow;int nowflow = 0;for(int k = list2[s] ;k; k = E[k].next){list2[s] = k;int to = E[k].to;int cost = E[k].cost;if(deep[to] != deep[s] + 1 || !cost) continue;int tmp = DFS_FLOW(to ,t ,minn(cost ,flow - nowflow));nowflow += tmp;E[k].cost -= tmp;E[k^1].cost += tmp;if(flow == nowflow)break;}if(!nowflow) list2[s] = 0;return nowflow; }int DINIC(int s ,int t ,int n) {int sum = 0;while(BFS(s ,t ,n)){ sum += DFS_FLOW(s ,t ,INF);}return sum; }void dfs(int s) {mark[s] = 1;num[++tt] = s;for(int k = list[s] ;k ;k = E[k].next){int to = E[k].to;if(E[k].cost && !mark[to])dfs(to);} }int find(int n ,int S ,int T) {E[list[S]].cost = 0;E[list[T - n]].cost= 0;int cout = 0;memset(mark ,0 ,sizeof(mark));while(1){ tt = 0;dfs(S);int ok = 1;for(int i = 1 ;i <= tt && ok ;i ++){ for(int k = list[num[i]] ;k && ok ;k = E[k].next)if(k % 2 == 0 && !mark[E[k].to] && !E[k].cost){ok = 0;S = E[k].to;cout ++;if(E[k].to == T)return cout;}}} }int main () {int n ,m ,S ,T ,i ,j ,a ,b ,c;while(~scanf("%d %d" ,&n ,&m)){memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&a ,&b);add(a + n + 1,b + 1, INF);}scanf("%d %d" ,&S ,&T);S ++ ,T ++;for(i = 1 ;i <= n ;i ++){if(i != S && i != T)add(i ,i + n ,1);else add(i ,i + n ,2);}T += n;int flow = DINIC(S ,T ,n + n);if(flow == 0) printf("%d\n" ,n);else if(flow == 2) puts("2");else printf("%d\n" ,find(n ,S ,T));}return 0; } 思路:(2)最短路,先跑一個最短路,記錄路徑,如果到不了T,那么就輸出n,如果能的話,來一個深搜,看看只跑非最短路上的點能不能到達T,如果能,那么就說明至少存在兩條不相交的路,那么直接輸出2,否則就是存在關鍵點的情況了,枚舉每一個關鍵點,通過非最短路上的點找到里關鍵點最遠的那個最短路上的點,那么這個點一定是關鍵點,然后在吧當前的這個點當下一步的關鍵點,就這樣一直找到T就行了..比最大流的那個好寫,思路都差不多.. 當前點a的下一個關鍵路徑是c,是最遠的那一個,如圖. #include<stdio.h> #include<string.h> #include<queue>#define N_node 110000 #define N_edge 330000 #define INF 1000000000 using namespace std;typedef struct {int to ,next ,cost; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int mer[N_node] ,S ,T; int s_x[N_node] ,mk_sx[N_node]; int mark[N_node];void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }bool SPFA(int s ,int t ,int n) {memset(mark ,0 ,sizeof(mark));for(int i = 0 ;i <= n ;i ++){s_x[i] = INF;mer[i] = i;}s_x[s] = 0;mark[s] = 1;queue<int>q;q.push(s);while(!q.empty()){int xin ,tou;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(s_x[xin] > s_x[tou] + E[k].cost){s_x[xin] = s_x[tou] + E[k].cost;mer[xin] = tou;if(!mark[xin]){mark[xin] = 1;q.push(xin);}}}}return s_x[t] != INF; }int ok; void DFS_1(int s) {for(int k = list[s] ;k ;k = E[k].next){int to = E[k].to;if(mark[to]|| ok) continue;if(to == T) ok = 1;if(mk_sx[to] || ok) continue;mark[to] = 1;DFS_1(to);} }int mk_id ,maxx; void DFS_2(int s) {for(int k = list[s] ;k ;k = E[k].next){int to = E[k].to;if(mark[to]) continue;if(mk_sx[to]){if(maxx < s_x[to]){maxx = s_x[to];mk_id = to;}continue ;}mark[to] = 1;DFS_2(to);} }int main () {int n ,m ,i ,j;int a ,b;while(~scanf("%d %d" ,&n ,&m)){memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&a ,&b);add(a + 1 ,b + 1 ,1);}scanf("%d %d" ,&S ,&T);S ++ ,T ++;if(!SPFA(S ,T ,n)){printf("%d\n" ,n);continue;}memset(mk_sx ,0 ,sizeof(mk_sx));int now = T;while(mer[now] != now){mk_sx[now] = 1;now = mer[now];}mk_sx[now] = 1;ok = 0;memset(mark ,0 ,sizeof(mark));mark[S] = 1;DFS_1(S);if(ok){puts("2");continue;}int sum = 1; memset(mark ,0 ,sizeof(mark));while(1){//mk_id ,maxx maxx = 0;mark[S] = 1;DFS_2(S);sum ++;S = mk_id;//printf("%d***\n" ,S); if(S == T) break;}printf("%d\n" ,sum);}return 0; }

總結

以上是生活随笔為你收集整理的hdu3313 最大流找关键点,或者最短路找关键点.的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。