转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4297581.html ---by 墨染之樱花
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3416
题目描述：求起点到终点一共有多少完全不同的最短路径（最短路径之间不能有公共边）
思路：先用dijkstra求出起点到终点的最短路，然后用可以成为最短路径的边（dis[终]-dis[始]==权值）建立网络，容量为1。最后只需求出以起点为源点终点为汇点的最大流即可
#include <iostream> #include <ios> #include <iomanip> #include <functional> #include <algorithm> #include <vector> #include <sstream> #include <list> #include <queue> #include <deque> #include <stack> #include <string> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <cstring> #include <climits> using namespace std; #define XINF INT_MAX #define INF 1<<30 #define MAXN 1000+10 #define eps 1e-8 #define zero(a) fabs(a)<eps #define sqr(a) ((a)*(a)) #define MP(X,Y) make_pair(X,Y) #define PB(X) push_back(X) #define PF(X) push_front(X) #define REP(X,N) for(int X=0;X<N;X++) #define REP2(X,L,R) for(int X=L;X<=R;X++) #define DEP(X,R,L) for(int X=R;X>=L;X--) #define CLR(A,X) memset(A,X,sizeof(A)) #define IT iterator #define PI acos(-1.0) #define test puts("OK"); #define _ ios_base::sync_with_stdio(0);cin.tie(0); typedef long long ll; typedef pair<int,int> PII; typedef priority_queue<int,vector<int>,greater<int> > PQI; typedef vector<PII> VII; typedef vector<int> VI; #define X first #define Y second int V,E; VII G2[MAXN]; int d[MAXN]; void dijkstra(int s) { priority_queue<PII,VII,greater<PII> > Q; fill(d,d+V,INF); d[s]=0; Q.push(MP(d[s],s)); while(!Q.empty()) { PII p=Q.top();Q.pop(); int v=p.Y; if(d[v]<p.X) continue; REP(i,G2[v].size()) { PII e=G2[v][i]; if(d[e.X]>d[v]+e.Y) { d[e.X]=d[v]+e.Y; Q.push(MP(d[e.X],e.X)); } } } } struct edge { int to; //终点 int cap; //容量 int rev; //反向边 edge(int t,int c,int r){to=t;cap=c;rev=r;} }; vector<edge> G[MAXN]; //存图 int level[MAXN]; //顶点到源点的距离标号 int iter[MAXN]; //当前弧，在其之前的边已经没有用了 int S,T; void add_edge(int from,int to,int cap) { edge e1(to,cap,G[to].size()); G[from].PB(e1); edge e2(from,0,G[from].size()-1); G[to].PB(e2); } //通过BFS计算从源点出发的距离标号 void bfs(int s) { CLR(level,-1); queue<int> Q; level[s]=0; Q.push(s); while(!Q.empty()) { int v=Q.front(); Q.pop(); REP(i,G[v].size()) { edge &e=G[v][i]; if(e.cap>0 && level[e.to]<0) { level[e.to]=level[v]+1; Q.push(e.to); } } } } int dfs(int v,int t,int f) { if(v==t) return f; for(int &i=iter[v];i<G[v].size();i++) { edge &e=G[v][i]; if(e.cap>0 && level[v]<level[e.to]) { int d=dfs(e.to,t,min(f,e.cap)); if(d>0) { e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int s,int t) { int flow=0; while(1) { bfs(s); if(level[t]<0) return flow; CLR(iter,0); int f; while((f=dfs(s,t,INF))>0) flow+=f; } } int main() {_ int P; scanf("%d",&P); while(P--) { CLR(G,0);CLR(G2,0); scanf("%d%d",&V,&E); REP(i,E) { int u,v,c; scanf("%d%d%d",&u,&v,&c); u--;v--; if(u!=v) G2[u].PB(MP(v,c)); } scanf("%d%d",&S,&T); S--;T--; dijkstra(S); if(d[T]==INF) { printf("0 "); continue; } REP(v,V) { REP(i,G2[v].size()) { PII e=G2[v][i]; int u=e.X,cost=e.Y; if(d[u]-d[v]==cost) add_edge(v,u,1); } } printf("%d ",max_flow(S,T)); } return 0; }