Marriage Match IV
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2470 Accepted Submission(s): 742 Problem Description
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
Author
starvae@HDU
Source
题意：
给出一张无向图，要求图上的不相交得最短路条数。
思路：
先求出单源最短路，从终点往起点倒着搜出最短路上的边（能够用双向链表）。然后另这些边的容量为1建新图。跑一遍最大流就可以。
#include#include #include #include using namespace std;#define N 1010#define M 101000const int INF = 1000000000;int n, m, sp, tp, cnte, cnte2, head[N], lowdis[N], head2[N], dep[N], tail[N];bool vis[N];class Edge{public: int u, v, w, next, next2;};Edge edge1[M*2], edge2[M*2];void addEdge1(int u, int v, int w){ edge1[cnte].u = u; edge1[cnte].v = v; edge1[cnte].w = w; edge1[cnte].next = head[u]; head[u] = cnte; edge1[cnte].next2 = tail[v]; tail[v] = cnte++;}void addEdge2(int u, int v, int w){ edge2[cnte2].u = u; edge2[cnte2].v = v; edge2[cnte2].w = w; edge2[cnte2].next = head2[u]; head2[u] = cnte2++; edge2[cnte2].v = u; edge2[cnte2].u = v; edge2[cnte2].w = 0; edge2[cnte2].next = head2[v]; head2[v] = cnte2++;}int spfa(){ queue q; for(int i = 1; i <= n; i++) { vis[i] = 0; lowdis[i] = INF; } vis[sp] = 1; lowdis[sp] = 0; q.push(sp); while(!q.empty()) { int cur = q.front(); q.pop(); vis[cur] = 0; for(int i = head[cur]; i != -1; i = edge1[i].next) { int v = edge1[i].v; if(lowdis[v] > lowdis[cur]+edge1[i].w) { lowdis[v] = lowdis[cur]+edge1[i].w; if(!vis[v]) { vis[v] = 1; q.push(v); } } } } return lowdis[tp] != INF;}void dfs(int cur){ for(int i = tail[cur]; i != -1; i = edge1[i].next2) { int u = edge1[i].u; if(lowdis[u]+edge1[i].w == lowdis[cur]) { addEdge2(u, cur, 1); if(!vis[u]) { vis[u] = 1; dfs(u); } } }}bool bfs(){ memset(vis, 0, sizeof vis); memset(dep, -1, sizeof dep); queue q; q.push(sp); vis[sp] = 1; dep[sp] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); for(int i = head2[cur]; i != -1; i = edge2[i].next) { int v = edge2[i].v; if(!vis[v] && edge2[i].w > 0) { dep[v] = dep[cur]+1; vis[v] = 1; q.push(v); } } } return dep[tp] != -1;}int dfs2(int cur, int flow){ if(cur == tp) return flow; int res = 0; for(int i = head2[cur]; i != -1 && flow > res; i = edge2[i].next) { int v = edge2[i].v; if(edge2[i].w > 0 && dep[v] == dep[cur]+1) { int x = min(edge2[i].w, flow-res); int f = dfs2(v, x); edge2[i].w-=f; edge2[i^1].w+=f; res += f; } } if(!res) dep[cur] = -1; return res;}int dinic(){ int res = 0; while(bfs()) { int t; while(t = dfs2(sp, INF)) { res += t; } } return res;}int main(){ //freopen("C:\\Users\\Admin\\Desktop\\in.txt", "r", stdin); int t; scanf("%d", &t); while(t--) { cnte = 0; cnte2 = 0; memset(head, -1, sizeof head); memset(head2, -1, sizeof head2); memset(tail, -1, sizeof tail); int u, v, w; scanf("%d%d", &n, &m); for(int i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &w); addEdge1(u, v, w); } scanf("%d%d", &sp, &tp); int ans; if(!spfa()) ans = 0; else { dfs(tp); ans = dinic(); } printf("%d\n", ans); } return 0;}