題意:
? ? ?給你一個無向圖,給你兩組起點和終點,問你這兩組起點和終點的最短路上最多有多少個交點...

思路:
? ? ?開一個數(shù)組dp[i][j]記錄最短路上i,j之間的點有多少個,這個數(shù)組是根據(jù)map[][]數(shù)組
更新的時候更新的,在floyd里,當(dāng)map[i][j] > map[i][k] + map[k][j] 時,
map[i][j] = map[i][k] + map[k][j] 同時 dp[i][j] = dp[i][k] + dp[k][j] - 1;
值得注意的是只有當(dāng)i,j都是最短路上的點的時候dp[i][j]才有意義,否則里面的數(shù)字沒意義,跑完Floyd以后dp里面的數(shù)組也就更新好了,然后暴力枚舉每一條同時都在兩條最短路上的點,取最大的那個就行了,提示:

當(dāng) map[s0][i] + map[i][j] + map[j][e0] == map[s0][e0]?

&&map[s1][i] + map[i][j] + mao[j][e1] == map[s1][e1] 的時候就說明i,j這兩個點同時在兩條最短路上.則 ans = maxx(ans ,dp[i][j]);

#include<stdio.h> #include<string.h>#define N 300 + 50 #define INF 1000000000 int map[N][N]; int dp[N][N];void Floyd(int n) {for(int k = 1 ;k <= n ;k ++)for(int i = 1 ;i <= n ;i ++)for(int j = 1 ;j <= n ;j ++){if(map[i][j] > map[i][k] + map[k][j]){map[i][j] = map[i][k] + map[k][j];dp[i][j] = dp[i][k] + dp[k][j] - 1;}}return ; }bool ok(int s0 ,int e0 ,int s1 ,int e1 ,int i ,int j) {return map[s0][i] + map[i][j] + map[j][e0] == map[s0][e0]&& map[s1][i] + map[i][j] + map[j][e1] == map[s1][e1]; }int main () {int n ,m ,i ,j;int a ,b ,c;int s0 ,s1 ,e1 ,e0;while(~scanf("%d %d" ,&n ,&m) && n + m){for(i = 1 ;i <= n ;i ++){for(j = i + 1 ;j <= n ;j ++)map[i][j] = map[j][i] = INF ,dp[i][j] = 0;map[i][i] = 0 ,dp[i][i] = 1;}for(i = 1 ;i <= m ;i ++){scanf("%d %d %d" ,&a ,&b ,&c);if(map[a][b] > c) map[a][b] = map[b][a] = c;dp[a][b] = dp[b][a] = 2;}scanf("%d %d %d %d" ,&s0 ,&e0 ,&s1 ,&e1);Floyd(n);int ans = 0;for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= n ;j ++)if(ok(s0 ,e0 ,s1 ,e1 ,i ,j) && ans < dp[i][j])ans = dp[i][j]; printf("%d\n" ,ans);}return 0;}

總結(jié)

以上是生活随笔為你收集整理的hdu2833 Floyd + dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。