题意：N个点M条边的有向图，给定起点S和终点T，求每条边都不重复的S-->T的最短路有多少条。
分析：首先第一步需要找出所有可能最短路上的边。怎么高效地求出呢？可以这样：先对起点S，跑出最短路；对于每条边 e（u，v，w)，若d[u]+w == d[v]。那么e就是最短路上的一条边。在前向星存储的图中遍历即可。网上还有题解用的方法是分别从S和T跑两次最短路，再判断d1[u]+d2[v]+w == d1[T]，其实思路是相似的，但是没必要多跑一遍。
用SPFA就会玄学超时，但其他人却没有；之后改用迪杰斯特拉就跑得很快。
之后问题可转化为求解S到T的最大流。将所求得的最短路的边，建新图，每条边的流量都是1。再用SAP求出S到T的最大流，即最终答案。
1#include<iostream> 2#include<cstring> 3#include<stdio.h> 4#include<vector> 5#include<string> 6#include<algorithm> 7#include<queue> 8#include<cmath> 9using namespace std; 10typedef int LL; 11 12const int maxn =1e3+5; 13const int maxm = 1e5+5; 14const LL INF =0x3f3f3f3f; 15struct Edge{ 16 int from,to; 17 LL val; 18}; 19struct HeapNode{ 20 LL d; //费用或路径 21 int u; 22 bool operator < (const HeapNode & rhs) const{return d > rhs.d;} 23}; 24struct Dijstra{ 25 int n,m; 26 vector<Edge> edges; 27 vector<int> G[maxn]; 28 bool used[maxn]; 29 LL d[maxn]; 30 int p[maxn]; 31 32 void init(int n){ 33 this->n = n; 34 for(int i=0;i<=n;++i) G[i].clear(); 35 edges.clear(); 36 memset(used,0,sizeof(used)); 37 } 38 39 void Addedge(int from,int to ,LL dist){ 40 edges.push_back((Edge){from,to,dist}); 41 m = edges.size(); 42 G[from].push_back(m-1); 43 } 44 45 void dijkstra(int s){ 46 priority_queue<HeapNode> Q; 47 for(int i=0;i<=n;++i) d[i]=INF; 48 d[s]=0; 49 Q.push((HeapNode){0,s}); 50 while(!Q.empty()){ 51 HeapNode x =Q.top();Q.pop(); 52 int u =x.u; 53 if(used[u]) 54 continue; 55 used[u]= true; 56 for(int i=0;i<G[u].size();++i){ 57 Edge & e = edges[G[u][i]]; 58 if(d[e.to] > d[u] + e.val){ 59 d[e.to] = d[u] +e.val; 60 p[e.to] = G[u][i]; 61 Q.push((HeapNode){d[e.to],e.to}); 62 } 63 } 64 } 65 } 66}G; 67 68 69const int MAXN=1010;//点数的最大值 70const int MAXM=200010;//边数的最大值 71 72struct Node{ 73 int from,to,next; 74 int cap; 75}; 76 77struct SAP_MaxFlow{ 78 int n,m; //点数和边数 79 int tol; 80 int head[MAXN]; 81 int dep[MAXN]; 82 int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y 83 Node edge[MAXM]; 84 85 void init(int N){ 86 this->n = N; 87 this->tol=0; 88 memset(head,-1,sizeof(head)); 89 } 90 91 void AddEdge(int u,int v,int w){ 92 edge[tol].from=u;edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];head[u]=tol++; 93 edge[tol].from=v;edge[tol].to=u;edge[tol].cap=0;edge[tol].next=head[v];head[v]=tol++; 94 } 95 96 void BFS(int start,int end) 97 { 98 memset(dep,-1,sizeof(dep)); 99 memset(gap,0,sizeof(gap)); 100 gap[0]=1; 101 int que[MAXN]; 102 int front,rear; 103 front=rear=0; 104 dep[end]=0; 105 que[rear++]=end; 106 while(front!=rear){ 107 int u=que[front++]; 108 if(front==MAXN)front=0; 109 for(int i=head[u];i!=-1;i=edge[i].next){ 110 int v=edge[i].to; 111 if(dep[v]!=-1)continue; 112 que[rear++]=v; 113 if(rear==MAXN)rear=0; 114 dep[v]=dep[u]+1; 115 ++gap[dep[v]]; 116 } 117 } 118 } 119 int SAP(int start,int end) 120 { 121 int res=0; 122 BFS(start,end); 123 int cur[MAXN]; 124 int S[MAXN]; 125 int top=0; 126 memcpy(cur,head,sizeof(head)); 127 int u=start; 128 int i; 129 while(dep[start]<n){ 130 if(u==end){ 131 int temp=INF; 132 int inser; 133 for(i=0;i<top;i++) 134 if(temp>edge[S[i]].cap){ 135 temp=edge[S[i]].cap; 136 inser=i; 137 } 138 for(i=0;i<top;i++){ 139 edge[S[i]].cap-=temp; 140 edge[S[i]^1].cap+=temp; 141 } 142 res+=temp; 143 top=inser; 144 u=edge[S[top]].from; 145 } 146 if(u!=end&&gap[dep[u]-1]==0)//出现断层，无增广路 147 break; 148 for(i=cur[u];i!=-1;i=edge[i].next) 149 if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1) 150 break; 151 if(i!=-1){ 152 cur[u]=i; 153 S[top++]=i; 154 u=edge[i].to; 155 } 156 else{ 157 int min=n; 158 for(i=head[u];i!=-1;i=edge[i].next){ 159 if(edge[i].cap==0)continue; 160 if(min>dep[edge[i].to]){ 161 min=dep[edge[i].to]; 162 cur[u]=i; 163 } 164 } 165 --gap[dep[u]]; 166 dep[u]=min+1; 167 ++gap[dep[u]]; 168 if(u!=start)u=edge[S[--top]].from; 169 } 170 } 171 return res; 172 } 173}F; 174 175//#define LOCAL 176int main() 177{ 178 #ifdef LOCAL 179 freopen("in.txt","r",stdin); 180 freopen("out.txt","w",stdout); 181 #endif 182 int N,M,s,t,u,v,T; 183 LL tmp,b; 184 scanf("%d",&T); 185 while(T--){ 186 scanf("%d%d",&N,&M); 187 G.init(N);F.init(N); 188 for(int i=1;i<=M;++i){ 189 scanf("%d%d%d",&u,&v,&tmp); 190 G.Addedge(u,v,tmp); 191 } 192 scanf("%d%d",&s,&t); 193 G.dijkstra(s); 194 for(int i=0;i<M;++i){ 195 Edge e = G.edges[i]; 196 if(G.d[e.from]+e.val==G.d[e.to]) 197 F.AddEdge(e.from,e.to,1); 198 } 199 printf("%d\n",F.SAP(s,t)); 200 } 201 return 0; 202}