题目链接 http://acm.hdu.edu.cn/showproblem.PHP?pid=3416
题意
N 个城市 M 条路径, 给定起点 A, 终点 B, 求有几条从 A 到 B 的最短路 (其中每经过的路径不能重复)
解题思路
先用最短路求出 A 到 B 的最短路 Min, 也求出 A 到每个城市的距离 dis[N], 然后反向求 B 到 A 的最短路, 得到 B 到每个城市的最短距离 dis2[N], 然后遍历每条路径 edge, 如果 dis[edge.from] + edge.len + dis2[edge.to]== Min, 就说明这条路径一定是 A 到 B 的最短路中会经过的路径,, 每条路径的容量为 1, 把每条符合条件的路径加入到最大流的图中, 建完图后, 以 A 为源点, B 为汇点跑最大流即可 (用 EdmondsKarp 会超时, 跑 Dinic 即可)
AC 代码
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> pii;
- const int maxn = 1e5+5;
- const int INF = 0x3f3f3f3f;
- struct Edge
- {
- int from,to,cap,flow;
- Edge(){}
- Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
- };
- struct Dinic
- {
- int n,m,s,t;
- vector<Edge> edges;
- vector G[maxn];
- bool vis[maxn];
- int d[maxn];
- int cur[maxn];
- void init(int n){
- for(int i=0;i<n;i++) G[i].clear();
- edges.clear();
- }
- void AddEdge(int from,int to,int cap){
- edges.push_back(Edge(from,to,cap,0));
- edges.push_back(Edge(to,from,0,0));
- m = edges.size();
- G[from].push_back(m-2);
- G[to].push_back(m-1);
- }
- bool BFS()
- {
- memset(vis,0,sizeof(vis));
- queue Q;
- Q.push(s);
- d[s] = 0;
- vis[s] = 1;
- while(!Q.empty()){
- int x = Q.front();
- Q.pop();
- for(int i=0;i<G[x].size();i++){
- Edge& e = edges[G[x][i]];
- if(!vis[e.to]&&e.cap> e.flow){
- vis[e.to] = 1;
- d[e.to] = d[x]+1;
- Q.push(e.to);
- }
- }
- }
- return vis[t];
- }
- int DFS(int x,int a){
- if(x==t || a==0)return a;
- int flow = 0,f;
- for(int &i=cur[x];i<G[x].size();i++){
- Edge& e = edges[G[x][i]];
- if(d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0){
- e.flow += f;
- edges[G[x][i]^1].flow -= f;
- flow += f;
- a -= f;
- if(a==0)break;
- }
- }
- return flow;
- }
- int Maxflow(int s,int t){
- this->s = s,this->t = t;
- int flow = 0;
- while(BFS()){
- memset(cur,0,sizeof(cur));
- flow += DFS(s,INF);
- }
- return flow;
- }
- };
- vector<Edge> G1[maxn];
- vector<Edge> G2[maxn];
- int N,M;
- int dis[maxn],dis2[maxn];
- bool vis[maxn];
- void dijkstra(int A,vector<Edge> G[maxn],int dis[maxn])
- {
- memset(vis,0,sizeof(vis));
- priority_queue<pii,vector,greater> Q;
- dis[A] = 0;
- Q.push(pii(dis[A],A));
- while(!Q.empty()){
- pii t = Q.top();
- Q.pop();
- int d = t.first;
- int u = t.second;
- for(int i=0;i<G[u].size();i++){
- Edge e = G[u][i];
- if(e.cap + d <dis[e.to]){
- dis[e.to] = e.cap + d;
- Q.push(pii(dis[e.to],e.to));
- }
- }
- }
- }
- int main(int argc, char const *argv[])
- {
- iOS::sync_with_stdio(false);
- cin.tie(0);
- int T = 0;
- cin>> T;
- Dinic ek;
- while(T--){
- cin>> N>> M;
- ek.init(N);
- for(int i=0;i<=N;i++){
- G1[i].clear();
- G2[i].clear();
- }
- int a,b,c;
- Edge e;
- for(int i=0;i<M;i++){
- cin>> a>> b>> c;
- e.from = a;
- e.to = b;
- e.cap = c;
- G1[e.from].push_back(e);
- swap(e.to,e.from);
- G2[e.from].push_back(e);
- }
- int A,B;
- cin>> A>> B;
- memset(dis,0x3f,sizeof(dis));
- dijkstra(A,G1,dis); // 正向跑最短路
- memset(dis2,0x3f,sizeof(dis2));
- int Min = dis[B];
- dijkstra(B,G2,dis2); // 反向跑最短路
- for(int i=1;i<=N;i++){
- for(int j=0;j<G1[i].size();j++){
- e = G1[i][j];
- if(dis[e.from] + e.cap + dis2[e.to]==Min){
- ek.AddEdge(e.from,e.to,1);
- }
- }
- }
- cout << ek.Maxflow(A,B) << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2793852.html