题意：给出一张n个点m条边的无向图( 2<=n<=1000, 0<=m<=100000 )和起点S、终点T。现在要求你每次从S出发都使用一条最短路到达T，并且每条路只能走一次。问最多可以从S走到T走几次最短路。
先处理出S到所有点的最短路，假设S到点i的最短路为d[i]。枚举每条边(from,to,cost)，如果d[to]=d[from]+cost，在新图中加一条边(from,to,1)，完了之后从S到T跑最大流。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #define INF 1<<30 7 #define maxn 1010 8 #define maxm 300000 9 using namespace std; 10 typedef pair<int,int> pii; 11 int v[maxm],next[maxm],w[maxm]; 12 int first[maxn],d[maxn],work[maxn],q[maxn]; 13 int e,S,T,N,M; 14 struct Edge{ 15 int from,to,dist; 16 }edge[100010]; 17 18 void init(){ 19 e = 0; 20 memset(first,-1,sizeof(first)); 21 } 22 23 void add_edge1(int a,int b,int c){ 24 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 25 } 26 27 void add_edge2(int a,int b,int c){ 28 //printf("add:%d to %d,cap = %d ",a,b,c); 29 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 30 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 31 } 32 33 void dijkstra(int src){ 34 priority_queue <pii,vector<pii>,greater<pii> > q; 35 memset(d,-1,sizeof(d)); 36 d[src] = 0; 37 q.push(make_pair(0,src)); 38 while(!q.empty()){ 39 while(!q.empty() && q.top().first > d[q.top().second]) q.pop(); 40 if(q.empty()) break; 41 int u = q.top().second; 42 q.pop(); 43 for(int i = first[u];i != -1;i = next[i]){ 44 if(d[v[i]] > d[u] + w[i] || d[v[i]] == -1){ 45 d[v[i]] = d[u] + w[i]; 46 q.push(make_pair(d[v[i]],v[i])); 47 } 48 } 49 } 50 } 51 52 int bfs(){ 53 int rear = 0; 54 memset(d,-1,sizeof(d)); 55 d[S] = 0;q[rear++] = S; 56 for(int i = 0;i < rear;i++){ 57 for(int j = first[q[i]];j != -1;j = next[j]) 58 if(w[j] && d[v[j]] == -1){ 59 d[v[j]] = d[q[i]] + 1; 60 q[rear++] = v[j]; 61 if(v[j] == T) return 1; 62 } 63 } 64 return 0; 65 } 66 67 int dfs(int cur,int a){ 68 if(cur == T) return a; 69 for(int &i = work[cur];i != -1;i = next[i]){ 70 if(w[i] && d[v[i]] == d[cur] + 1) 71 if(int t = dfs(v[i],min(a,w[i]))){ 72 w[i] -= t;w[i^1] += t; 73 return t; 74 } 75 } 76 return 0; 77 } 78 79 int dinic(){ 80 int ans = 0; 81 while(bfs()){ 82 memcpy(work,first,sizeof(first)); 83 while(int t = dfs(S,INF)) ans += t; 84 } 85 return ans; 86 } 87 88 int main() 89 { 90 int kase; 91 scanf("%d",&kase); 92 while(kase--){ 93 init(); 94 scanf("%d%d",&N,&M); 95 for(int i = 0;i < M;i++){ 96 int a,b,c; 97 scanf("%d%d%d",&a,&b,&c); 98 add_edge1(a,b,c); 99 edge[i].from = a; 100 edge[i].to = b; 101 edge[i].dist = c; 102 } 103 scanf("%d%d",&S,&T); 104 dijkstra(S); 105 //for(int i = 1;i <= N;i++) 106 // printf("d[%d] = %d ",i,d[i]); 107 init(); 108 for(int i = 0;i < M;i++){ 109 int from = edge[i].from; 110 int to = edge[i].to; 111 int dist = edge[i].dist; 112 if(d[to] == d[from] + dist) 113 add_edge2(from,to,1); 114 } 115 int ans = dinic(); 116 printf("%d ",ans); 117 } 118 return 0; 119 }