HDU3416(KB11-O spfa+最大流)

Marriage Match IV

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4381 Accepted Submission(s): 1310

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

HDOJ Monthly Contest – 2010.06.05

只有最短路上的边才加入网络，容量都为1，跑最大流

  1 //2017-08-25
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <queue>
  7 
  8 using namespace std;
  9 
 10 const int N = 5010;
 11 const int M = 500000;
 12 const int INF = 0x3f3f3f3f;
 13 int head[N], tot;
 14 struct Edge{
 15     int next, to, w;
 16 }edge[M];
 17 
 18 void add_edge(int u, int v, int w){
 19     edge[tot].w = w;
 20     edge[tot].to = v;
 21     edge[tot].next = head[u];
 22     head[u] = tot++;
 23 }
 24 
 25 struct Dinic{
 26     int level[N], S, T;
 27     void init(){
 28         tot = 0;
 29         memset(head, -1, sizeof(head));
 30     }
 31     void set_s_t(int _S, int _T){
 32         S = _S;
 33         T = _T;
 34     }
 35     bool bfs(){
 36         queue<int> que;
 37         memset(level, -1, sizeof(level));
 38         level[S] = 0;
 39         que.push(S);
 40         while(!que.empty()){
 41             int u = que.front();
 42             que.pop();
 43             for(int i = head[u]; i != -1; i = edge[i].next){
 44                 int v = edge[i].to;
 45                 int w = edge[i].w;
 46                 if(level[v] == -1 && w > 0){
 47                     level[v] = level[u]+1;
 48                     que.push(v);
 49                 }
 50             }
 51         }
 52         return level[T] != -1;
 53     }
 54     int dfs(int u, int flow){
 55         if(u == T)return flow;
 56         int ans = 0, fw;
 57         for(int i = head[u]; i != -1; i = edge[i].next){
 58             int v = edge[i].to, w = edge[i].w;
 59             if(!w || level[v] != level[u]+1)
 60               continue;
 61             fw = dfs(v, min(flow-ans, w));
 62             ans += fw;
 63             edge[i].w -= fw;
 64             edge[i^1].w += fw;
 65             if(ans == flow)return ans;
 66         }
 67         if(ans == 0)level[u] = 0;
 68         return ans;
 69     }
 70     int maxflow(){
 71         int flow = 0;
 72         while(bfs())
 73           flow += dfs(S, INF);
 74         return flow;    
 75     }
 76 }dinic;
 77 
 78 //dis[0][u]表示从起点到u的最短距离，dis[1][u]表示从终点到u的最短距离，cnt[u]记录u入队次数，判负环用
 79 int dis[2][N], cnt[N];
 80 bool vis[N];
 81 bool spfa(int s, int n, int op){
 82     memset(vis, false, sizeof(vis));
 83     memset(dis[op], INF, sizeof(dis));
 84     memset(cnt, 0, sizeof(cnt));
 85     vis[s] = true;
 86     dis[op][s] = 0;
 87     cnt[s] = 1;
 88     queue<int> q;
 89     q.push(s);
 90     while(!q.empty()){
 91         int u = q.front();
 92         q.pop();
 93         vis[u] = false;
 94         for(int i = head[u]; i != -1; i = edge[i].next){
 95             int v = edge[i].to;
 96             int w = edge[i].w;
 97             if(dis[op][v] > dis[op][u] + w){
 98                 dis[op][v] = dis[op][u] + w;
 99                 if(!vis[v]){
100                     vis[v] = true;
101                     q.push(v);
102                     if(++cnt[v] > n)return false;
103                 }
104             }
105         }
106     }
107     return true;
108 }
109 
110 struct Line{
111     int u, v, w;
112 }line[M];
113 
114 int main()
115 {
116     std::ios::sync_with_stdio(false);
117     //freopen("inputO.txt", "r", stdin);
118     int T, n, m, A, B;
119     cin>>T;
120     while(T--){
121         cin>>n>>m;
122         int u, v, w;
123         for(int i = 0; i < m; i++)
124           cin>>line[i].u>>line[i].v>>line[i].w;
125         cin>>A>>B;
126         dinic.init();
127         for(int i = 0; i < m; i++)
128           add_edge(line[i].u, line[i].v, line[i].w);
129         spfa(A, n, 0);//求从起点开始到各个点的最短路
130         dinic.init();
131         for(int i = 0; i < m; i++)
132           add_edge(line[i].v, line[i].u, line[i].w);
133         spfa(B, n, 1);//求从终点开始到各个点的最短路
134         dinic.init();
135         dinic.set_s_t(A, B);
136         for(int i = 0; i < m; i++){
137             u = line[i].u;
138             v = line[i].v;
139             w = line[i].w;
140             //只有最短路上的边才加入网络
141             if(dis[0][u]+dis[1][v]+w == dis[0][B]){
142                 add_edge(u, v, 1);
143                 add_edge(v, u, 0);
144             }
145         }
146         cout<<dinic.maxflow()<<endl;
147     }
148     return 0;
149 }