hdu2833 Floyd + dp
DP Floyd
2023-09-11 14:13:59 时间
题意:
给你一个无向图,给你两组起点和终点,问你这两组起点和终点的最短路上最多有多少个交点...
思路:
开一个数组dp[i][j]记录最短路上i,j之间的点有多少个,这个数组是根据map[][]数组
更新的时候更新的,在floyd里,当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;
值得注意的是只有当i,j都是最短路上的点的时候dp[i][j]才有意义,否则里面的数字没意义,跑完Floyd以后dp里面的数组也就更新好了,然后暴力枚举每一条同时都在两条最短路上的点,取最大的那个就行了,提示:
给你一个无向图,给你两组起点和终点,问你这两组起点和终点的最短路上最多有多少个交点...
思路:
开一个数组dp[i][j]记录最短路上i,j之间的点有多少个,这个数组是根据map[][]数组
更新的时候更新的,在floyd里,当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;
值得注意的是只有当i,j都是最短路上的点的时候dp[i][j]才有意义,否则里面的数字没意义,跑完Floyd以后dp里面的数组也就更新好了,然后暴力枚举每一条同时都在两条最短路上的点,取最大的那个就行了,提示:
当 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; }
相关文章
- hdu 1160 上升序列 dp
- Bomb(要49)--数位dp
- DP的学习
- Java实现 LeetCode 801 使序列递增的最小交换次数 (DP)
- hdu 3652数位dp
- 数塔dp -A
- Codeforces 544E Remembering Strings 状压dp
- HDU-4628 Pieces 如压力DP
- BZOJ 2878([Noi2012]-失落的游乐园树DP+出站年轮加+后市展望DP+vector的erase)
- Codeforces 479E Riding in a Lift(dp)
- POJ3254 Corn Fields 状态压缩DP
- [状压dp] hdu 4064 Carcassonne
- poj2533--Longest Ordered Subsequence(dp:最长上升子序列)
- wikioi 1163 訪问艺术馆 树形dp
- 377. Combination Sum IV——DP本质:针对结果的迭代,dp[ans] <= dp[ans-i] & dp[i] 找三者关系 思考问题的维度+1,除了数据集迭代还有考虑结果
- 适合新手入门的DP题总结【精选洛谷题集30道】