題意： 有 n 個城市，知道了起點和終點，有 m 條有向邊，問從起點到終點的最短路一共有多少條。

解題思路：這題的關鍵就是找到哪些邊可以構成最短路，其實之前做最短路的題目接觸過很多，反向建一個圖，求兩邊最短路，即從src到任一點的最短路dis1[]和從des到任一點的最短路dis2[]，那么假設這條邊是(u,v,w)，如果dis1[u] + w + dis2[v] = dis1[des],說明這條邊是構成最短路的邊。找到這些邊，就可以把邊的容量設為1，跑一邊最大流即可。

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;const int maxn = 1005; const int inf = 0x3f3f3f3f; struct Edge {int from,to,next,w; }edge[800005],E[100005]; int n,m,st,ed; int cnt,head[maxn],pre[2][maxn]; int dis[2][maxn],level[maxn]; bool inq[maxn];void addedge(int u,int v,int w) {edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++;swap(u,v);edge[cnt].to = v;edge[cnt].w = 0;edge[cnt].next = head[u];head[u] = cnt++; }void addedge1(int u,int v,int w) {edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = pre[0][u];pre[0][u] = cnt++; }void addedge2(int u,int v,int w) {edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = pre[1][u];pre[1][u] = cnt++; }void build() {int u,v,w;memset(head,-1,sizeof(head));for(int i = 1; i <= m; i++){u = E[i].from, v = E[i].to, w = E[i].w;if(dis[0][u] + w + dis[1][v] == dis[0][ed])addedge(u,v,1);} }void spfa(int src,int des,int idx) {queue<int> q;memset(dis[idx],inf,sizeof(dis[idx]));memset(inq,false,sizeof(inq));dis[idx][src] = 0;q.push(src);inq[src] = true;while(!q.empty()){int u = q.front();q.pop();inq[u] = false;for(int i = pre[idx][u]; i != -1; i = edge[i].next){int v = edge[i].to;if(dis[idx][v] > dis[idx][u] + edge[i].w){dis[idx][v] = dis[idx][u] + edge[i].w;if(inq[v] == false){inq[v] = true;q.push(v);}}}} }int BFS(int src,int des){queue<int> q;memset(level,0,sizeof(level));level[src]=1;q.push(src);while(!q.empty()){int u = q.front();q.pop();if(u==des) return 1;for(int k = head[u];k!=-1;k=edge[k].next){int v = edge[k].to,w=edge[k].w;if(level[v]==0 && w!=0){level[v]=level[u]+1;q.push(v);}}}return -1; } int dfs(int u,int des,int increaseRoad){if(u==des) return increaseRoad;int ret=0;for(int k=head[u];k!=-1;k=edge[k].next){int v = edge[k].to,w=edge[k].w;if(level[v]==level[u]+1&&w!=0){int MIN = min(increaseRoad-ret,w);w = dfs(v,des,MIN);if(w > 0){edge[k].w -=w;edge[k^1].w+=w;ret+=w;if(ret==increaseRoad) return ret;}else level[v] = -1; }}return ret; } int Dinic(int src,int des){int ans = 0;while(BFS(src,des)!=-1) ans+=dfs(src,des,inf);return ans; }int main() {int t,u,v,w;scanf("%d",&t);while(t--){cnt = 0;memset(pre,-1,sizeof(pre));scanf("%d%d",&n,&m);for(int i = 1; i <= m; i++){scanf("%d%d%d",&u,&v,&w);E[i].from = u,E[i].to = v,E[i].w = w;addedge1(u,v,w);addedge2(v,u,w);}scanf("%d%d",&st,&ed);spfa(st,ed,0);spfa(ed,st,1);build();int maxflow = Dinic(st,ed);printf("%d\n",maxflow);}return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

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

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