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，跑最大流

 //2017-08-25

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int N = ;

 const int M = ;

 const int INF = 0x3f3f3f3f;

 int head[N], tot;

 struct Edge{

     int next, to, w;

 }edge[M];

 void add_edge(int u, int v, int w){

     edge[tot].w = w;

     edge[tot].to = v;

     edge[tot].next = head[u];

     head[u] = tot++;

 }

 struct Dinic{

     int level[N], S, T;

     void init(){

         tot = ;

         memset(head, -, sizeof(head));

     }

     void set_s_t(int _S, int _T){

         S = _S;

         T = _T;

     }

     bool bfs(){

         queue<int> que;

         memset(level, -, sizeof(level));

         level[S] = ;

         que.push(S);

         while(!que.empty()){

             int u = que.front();

             que.pop();

             for(int i = head[u]; i != -; i = edge[i].next){

                 int v = edge[i].to;

                 int w = edge[i].w;

                 if(level[v] == - && w > ){

                     level[v] = level[u]+;

                     que.push(v);

                 }

             }

         }

         return level[T] != -;

     }

     int dfs(int u, int flow){

         if(u == T)return flow;

         int ans = , fw;

         for(int i = head[u]; i != -; i = edge[i].next){

             int v = edge[i].to, w = edge[i].w;

             if(!w || level[v] != level[u]+)

               continue;

             fw = dfs(v, min(flow-ans, w));

             ans += fw;

             edge[i].w -= fw;

             edge[i^].w += fw;

             if(ans == flow)return ans;

         }

         if(ans == )level[u] = ;

         return ans;

     }

     int maxflow(){

         int flow = ;

         while(bfs())

           flow += dfs(S, INF);

         return flow;

     }

 }dinic;

 //dis[0][u]表示从起点到u的最短距离，dis[1][u]表示从终点到u的最短距离，cnt[u]记录u入队次数，判负环用

 int dis[][N], cnt[N];

 bool vis[N];

 bool spfa(int s, int n, int op){

     memset(vis, false, sizeof(vis));

     memset(dis[op], INF, sizeof(dis));

     memset(cnt, , sizeof(cnt));

     vis[s] = true;

     dis[op][s] = ;

     cnt[s] = ;

     queue<int> q;

     q.push(s);

     while(!q.empty()){

         int u = q.front();

         q.pop();

         vis[u] = false;

         for(int i = head[u]; i != -; i = edge[i].next){

             int v = edge[i].to;

             int w = edge[i].w;

             if(dis[op][v] > dis[op][u] + w){

                 dis[op][v] = dis[op][u] + w;

                 if(!vis[v]){

                     vis[v] = true;

                     q.push(v);

                     if(++cnt[v] > n)return false;

                 }

             }

         }

     }

     return true;

 }

 struct Line{

     int u, v, w;

 }line[M];

 int main()

 {

     std::ios::sync_with_stdio(false);

     //freopen("inputO.txt", "r", stdin);

     int T, n, m, A, B;

     cin>>T;

     while(T--){

         cin>>n>>m;

         int u, v, w;

         for(int i = ; i < m; i++)

           cin>>line[i].u>>line[i].v>>line[i].w;

         cin>>A>>B;

         dinic.init();

         for(int i = ; i < m; i++)

           add_edge(line[i].u, line[i].v, line[i].w);

         spfa(A, n, );//求从起点开始到各个点的最短路

         dinic.init();

         for(int i = ; i < m; i++)

           add_edge(line[i].v, line[i].u, line[i].w);

         spfa(B, n, );//求从终点开始到各个点的最短路

         dinic.init();

         dinic.set_s_t(A, B);

         for(int i = ; i < m; i++){

             u = line[i].u;

             v = line[i].v;

             w = line[i].w;

             //只有最短路上的边才加入网络

             if(dis[][u]+dis[][v]+w == dis[][B]){

                 add_edge(u, v, );

                 add_edge(v, u, );

             }

         }

         cout<<dinic.maxflow()<<endl;

     }

     return ;

 }

巴特西

HDU3416(KB11-O spfa+最大流)