本文共 1705 字，大约阅读时间需要 5 分钟。
大意：给定一张M条边的无向带权图，求从起点S到终点E恰好经过K条边的最短路径。2<=M<=100,2<=K<=1000000。保证每个连边的点度至少为2.
思路：参见2008国家集训队论文day1 《矩阵乘法在信息学中的应用》俞华程。
设计一个相似的动态规划的算法：
g[i][j] = ∑g[i-1][k]·G[k][j]
其中g[i][j]表示有多少通过i条边的路径能到达点j。
同样，我们可以重新定义矩阵乘法为：
C[i][j] = min(A[i][k]·B[k][j]).（1<=k<=b）
其中 · 代表A矩阵和B矩阵进行一次Floyd求min操作。
把给定的图转换为邻接矩阵，如果i->j对应有边则赋值边权，否则赋值为无穷大，C[i][j] = min(A[i][k]·A[k][j])，对应于从i->j经过两条路径的最短路径。同理：我们只需进行K-1次操作即可得到最终的答案矩阵。
#include #include #include #include #include #include #include #include #include #include #include using namespace std;const int maxn = 110;const int INF = 0x3f3f3f3f;map Map;typedef struct Matrix{ int m[maxn][maxn]; void init() { memset(m, INF, sizeof(m)); }}Ma;int k, n, m, s, e;void init(){ n = 0; Map.clear();}Ma Floyd(Ma A, Ma B){ Ma C; C.init(); for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(C.m[i][j] > A.m[i][k] + B.m[k][j]) C.m[i][j] = A.m[i][k] + B.m[k][j]; } } } return C;}Ma power(Ma A, int k){ if(k == 0) return A; Ma ans = A; while(k) { if(k & 1) { ans = Floyd(ans, A); } A = Floyd(A, A); k /= 2; } return ans;}Ma A;void read_case(){ init(); A.init(); for(int i = 0; i < m; i++) { int x, y, w; scanf("%d%d%d", &w, &x, &y); if(!Map[x]) Map[x] = ++n; if(!Map[y]) Map[y] = ++n; int u = Map[x], v = Map[y]; if(w < A.m[u][v]) { A.m[u][v] = A.m[v][u] = w; } }}void solve(){ read_case(); Ma ans; ans = power(A, k-1); printf("%d\n", ans.m[Map[s]][Map[e]]);}int main(){ while(~scanf("%d%d%d%d", &k, &m, &s, &e)) { solve(); } return 0;}
转载于:https://www.cnblogs.com/Buck-Meister/archive/2013/04/24/3039965.html
View Code