题意:求A到B不同最短路的条数(即边不能重复走, 点可以多次走)
分析:先从A跑最短路,再从B跑最短路,如果d(A -> u) + w (u, v) + d (B -> v) == shortest path,那么这条边就是有用边(在最短路中),利用这个性质重新建最大流的图,然后增广路算法Dinic求出最多有多少条最短路.SPFA + Dinic 组合已经见过一次了
#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 5; const int M = 1e5 + 5; const int INF = 0x3f3f3f3f; struct Edge { int u, v, w, nex; Edge() {} Edge(int u, int v, int w, int nex) : u (u), v (v), w (w), nex (nex) {} }edge[2][M]; struct Flow { int v, cap, rev; Flow() {} Flow(int v, int cap, int rev) : v (v), cap (cap), rev (rev) {} }; vector<Flow> F[N]; int it[N]; int lv[N]; int head[2][N]; int d[2][N]; bool vis[N]; int n, m, e[2]; int a, b, sp; void init(int id) { memset (head[id], -1, sizeof (head[id])); e[id] = 0; } void add_edge(int u, int v, int w, int id) { edge[id][e[id]] = Edge (u, v, w, head[id][u]); head[id][u] = e[id]++; } void re_edge(void) { init (1); for (int i=0; i<e[0]; ++i) { add_edge (edge[0][i].v, edge[0][i].u, edge[0][i].w, 1); } } void add_flow_edge(int u, int v, int cap) { F[u].push_back (Flow (v, cap, (int) F[v].size ())); F[v].push_back (Flow (u, 0, (int) F[u].size ()-1)); } void BFS(int s) { memset (lv, -1, sizeof (lv)); queue<int> que; que.push (s); lv[s] = 0; while (!que.empty ()) { int u = que.front (); que.pop (); for (int i=0; i<F[u].size (); ++i) { Flow &e = F[u][i]; if (e.cap > 0 && lv[e.v] < 0) { lv[e.v] = lv[u] + 1; que.push (e.v); } } } } int DFS(int u, int t, int f) { if (u == t) return f; for (int &i=it[u]; i<F[u].size (); ++i) { Flow &e = F[u][i]; if (e.cap > 0 && lv[u] < lv[e.v]) { int d = DFS (e.v, t, min (f, e.cap)); if (d > 0) { e.cap -= d; F[e.v][e.rev].cap += d; return d; } } } return 0; } //最大流算法 int Dinic(int s, int t) { int flow = 0, f; for (; ;) { BFS (s); if (lv[t]< 0) return flow; memset (it, 0, sizeof (it)); while ((f = DFS (s, t, INF)) > 0) flow += f; } } void build_max_flow_graph(void) { for (int i=1; i<=n; ++i) F[i].clear (); for (int i=0; i<m; ++i) { Edge &e = edge[0][i]; if (d[0][e.u] + e.w + d[1][e.v] == sp) { add_flow_edge (e.u, e.v, 1); add_flow_edge (e.v, e.u, 0); } } } void SPFA(int s, int id) { memset (d[id], INF, sizeof (d[id])); memset (vis, false, sizeof (vis)); d[id][s] = 0; vis[s] = true; queue<int> que; que.push (s); while (!que.empty ()) { int u = que.front (); que.pop (); vis[u] = false; for (int i=head[id][u]; ~i; i=edge[id][i].nex) { int v = edge[id][i].v, w = edge[id][i].w; if (d[id][v] > d[id][u] + w) { d[id][v] = d[id][u] + w; if (!vis[v]) { vis[v] = true; que.push (v); } } } } } int run(void) { SPFA (a, 0); sp = d[0][b]; if (sp == INF) return 0; re_edge (); SPFA (b, 1); build_max_flow_graph (); return Dinic (a, b); } int main(void) { int T; scanf ("%d", &T); while (T--) { init (0); scanf ("%d%d", &n, &m); for (int u, v, w, i=1; i<=m; ++i) { scanf ("%d%d%d", &u, &v, &w); add_edge (u, v, w, 0); } scanf ("%d%d", &a, &b); printf ("%d ", run ()); } return 0; }