# Q - Marriage Match IV

Do not sincere non-interference. Like that show, now starvae also

take part in a show, but it take place between city A and B. Starvae

is in city A and girls are in city B. Every time starvae can get to

city B and make a data with a girl he likes. But there are two

problems with it, one is starvae must get to B within least time, it's

said that he must take a shortest path. Other is no road can be taken

more than once. While the city starvae passed away can been taken more

than once.So, under a good RP, starvae may have many chances to get to city B.

But he don't know how many chances at most he can make a data with the

girl he likes . Could you help starvae? Input The first line is an

integer T indicating the case number.(1<=T<=65) For each case,there

are two integer n and m in the first line ( 2<=n<=1000, 0<=m<=100000 )

,n is the number of the city and m is the number of the roads.Then follows m line ,each line have three integers

a,b,c,(1<=a,b<=n,0<c<=1000)it means there is a road from a to b and

it's distance is c, while there may have no road from b to a. There

may have a road from a to a,but you can ignore it. If there are two

roads from a to b, they are different.At last is a line with two integer A and B(1<=A,B<=N,A!=B), means the

number of city A and city B. There may be some blank line between

each case. Output Output a line with a integer, means the chances

starvae can get at most. Sample Input

3 7 8 1 2 1 1 3 1 2 4 1 3 4 1 4 5 1 4 6 1 5 7 1 6 7 1 1 7 6 7 1 2 1 2 3 1 1 3 3 3 4 1 3 5 1 4 6 1 5 6 1 1 6 2 2 1 2 1 1 2 2 1 2 Sample Output 2 1 1

- There are several shortest paths for A person from city A to city B. here we need to pay special attention to: each path can only be taken once, and after that, we can't go any more, and we can only take the shortest path
- Idea: remove the points and edges that are not the shortest path (there may be several shortest paths here), and re create a new graph with the remaining edges. Set the edge weight to 1, and run the maximum flow once.

So how can we judge whether an edge is the edge of the shortest path?

Let's make some assumptions first:

- Suppose the edge to be judged is (u, v), its length is w (u, v), the source point of the graph is s, and the sink point is e.
- The shortest distance from s to other points of the shortest to forward running is stored in the dis1 [] array,

Dis [u] is the shortest distance from s to u; - The shortest distance from e to other points in the dis2 [] array is the shortest distance from u to e (note that this direction is u to v)

- Finally, we just need to traverse each given edge:

If dis1 [u] + W (U, V) + dis2 [v] = dis1 [e] is true. Then we can judge that this edge is the edge of the shortest path.

Finally, we can get the number of path schemes by running the maximum flow of these edge new graphs. - In fact, we have to consider the rest: why does the biggest stream come out with the answer?????????

## Problem solving (SPFA + ISAP)

#include<iostream> #include<queue> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f const int maxn = 10005; const int maxm = 200005; struct Edge { int v,w,next; } edge1[maxm], edge2[maxm], edge[maxm]; int n,m,s,e; int head1[maxn], head2[maxn], head[maxn]; int dis1[maxn], dis2[maxn]; int use[maxn]; int k1,k2,k; void Add(int u, int v, int w, int head[], int & k, Edge edge[]) { edge[++ k] = (Edge){ v, w, head[u]}; head[u] = k; } void Spfa(int s, int dis[], int head[], Edge edge[]) { for(int i = 1; i <= n; i ++) dis[i] = INF,use[i] = 0; dis[s] = 0; queue<int> q; q.push(s); int u,v,w; while(! q.empty()) { u = q.front(); q.pop(); use[u] = 0; for(int i = head[u]; i != -1; i = edge[i].next) { v = edge[i].v; w = edge[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if(! use[v]) { q.push(v); use[v] = 1; } } } } } int deep[maxn], num[maxn]; int cur[maxn], last[maxm]; void bfs(int e) { for(int i = 0; i <= n; i ++) deep[i] = n, cur[i] = head[i], use[i] = 0; deep[e] = 0; queue<int> q; q.push(e); int u, v; while(! q.empty()) { u = q.front(); q.pop(); // use[u] = 0; for(int i = head[u]; i != -1; i = edge[i].next) { v = edge[i].v; if(edge[i^1].w && deep[v] == n) //The positive graph edge exists and the node v has not been found { deep[v] = deep[u] + 1; q.push(v); // if(! use[v]) // { // q.push(v); // use[v] = 1; // } } } } } int Add_flow(int s, int e) { int ans = INF; int now = e; while(now != s) { ans = min(ans, edge[last[now]].w); now = edge[last[now]^1].v; } now = e; while(now != s) { edge[last[now]].w -= ans; edge[last[now]^1].w += ans; now = edge[last[now]^1].v; } return ans; } int isap(int s, int e) { int now = s; //Start from the starting point bfs(e); //First, find out a polishing path with the edge being operated for(int i = 1; i <= n; i ++) num[deep[i]] ++; int mx_flw = 0; while(deep[s] < n) { if(now == e) //If it reaches the convergence point and expands directly, it will return to the source point for the next round of augmentation { mx_flw += Add_flow(s, e); now = s; } bool has_find = 0; for(int i = cur[now]; i != -1; i = edge[i].next) { if(edge[i].w && deep[now] == deep[edge[i].v] + 1) { has_find = 1; //Marking has found a way cur[now] = i; //Optimize current arc now = edge[i].v; last[edge[i].v] = i; break; } } if(! has_find) { int minn = n - 1; for(int i = head[now]; i != -1; i = edge[i].next) if(edge[i].w) minn = min(minn, deep[edge[i].v]); if( (-- num[deep[now]]) == 0) break; //gap optimization leads to fault num[deep[now] = minn + 1] ++; cur[now] = head[now]; if(now != s) now = edge[last[now]^1].v; } } return mx_flw; } void init() { k1 = 0; k2 = 0; k = -1; for(int i = 0; i <= n; i ++) head1[i] = -1, head2[i] = -1, head[i] = -1; memset(num, 0, sizeof(num)); } int main() { //freopen("T.txt","r",stdin); int t; scanf("%d", &t); while(t --) { scanf("%d %d", &n, &m); init(); int u, v, w; for(int i = 1; i <= m; i ++) { scanf("%d %d %d", &u, &v, &w); Add(u, v, w, head1, k1, edge1); Add(v, u, w, head2, k2, edge2); } scanf("%d %d", &s, &e); Spfa(s, dis1, head1, edge1); Spfa(e, dis2, head2, edge2); //Go through all the edges in the graph to find the shortest edge for(int i = 1; i <= m; i ++) { u = edge2[i].v; v = edge1[i].v; w = edge1[i].w; if(dis1[u] + w + dis2[v] == dis1[e]) { Add(u, v, 1, head, k, edge); Add(v, u, 0, head, k, edge); } } printf("%d\n", isap(s, e)); } reurn 0; }