Marriage Match IV



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
题意:给出点跟边,点之间存在重边,有个人想从起点到终点。
求:从起点在保证最短路值的条件下有多少条弱独立轨(即边只能经过一次,但点能通过多次)能到终点。
分析:题意从起点到终点,问多少条弱独立轨,显然就是最大流。
点之间允许重边,那权值小的边肯定能制造出更短的路径,于是对每两点间,只需要保存权值最小的边,但最小的边也有重边,所以可以每两个点间的最小边数。那这两个点就可以被经过的次数就是最小边数了。
接下来就是确定哪些边是在最短路上的边了。这个要求建两次图,题意中给出了起点s跟终点t。一次是按原图,计算所有点到s的最短路dis1;另一次是将图反过来,计算所有点到t的最短路dis2;接下来对某个边(a,b).如果dis1[a] + dis2[b] + w(a,b) == dis1[t];则表示这个条边在最短路上。将所有这些在最短路上的边建成一个图,容量是每两个点间的最少边数。最大流即为答案。
代码:
#include <stdio.h>  
#include 
<string.h> 
#include 
<queue> 
#include 
<algorithm>
#include 
<iostream>
#define Min(a, b) (a) < (b) ? a : b  
#define Max(a, b) (a) > (b) ? a : b
using  namespace std;  
const  int MAXN = 2005;  
const  int MAXM = 210000;  
const  int INF = 1100000000;  
struct  Edge  
{  
    
int  st, ed;  
    
int  next;  
    
int  flow; 
    
int cap; 
}edge[MAXM]; 
int  head[MAXN], level[MAXN], que[MAXN], E;
void  add(int u, int v, int w)  
{  
    edge[E].flow 
= 0;  
    edge[E].cap 
= w;
    edge[E].st 
= u;  
    edge[E].ed 
= v;  
    edge[E].next 
= head[u];  
    head[u] 
= E++;      
    edge[E].flow 
= 0
    edge[E].cap 
= 0
    edge[E].st 
= v;  
    edge[E].ed 
= u;  
    edge[E].next 
= head[v];  
    head[v] 
= E++;  
}
int  dinic_bfs(int src, int dest, int ver)        
{        
    
int i, j;         
    
for (i = 0; i <= ver; i++)
    {    
        level[i] 
= -1;
    }
    
int rear = 1;        
    que[
0= src; level[src] = 0;        
    
for(i = 0; i < rear; i++
    {        
          
for(j = head[que[i]]; j != -1; j = edge[j].next)
         {        
            
if(level[edge[j].ed] == -1 && edge[j].cap > edge[j].flow)        
            {        
              level[edge[j].ed] 
= level[que[i]]+1;        
              que[rear
++= edge[j].ed;        
            }
         }
    }
    
return  level[dest] >= 0;        
}        
     
int dinic_dfs(int src, int dest, int ver)        
{        
    
int stk[MAXN], top = 0;        
    
int ret = 0, cur, ptr, pre[MAXN], minf, i;        
    
int del[MAXN];        
    
for (i = 0; i <= ver; i++
    {
        del[i] 
= 0;
    }
    stk[top
++= src;         
    pre[src] 
= src; 
    cur 
= src;        
    
while(top)        
    {        
        
while(cur != dest && top)        
        {        
            
for(i = head[cur]; i != -1; i = edge[i].next)        
            {        
                
if(level[edge[i].ed] == level[cur] + 1 && edge[i].cap > edge[i].flow  && !del[edge[i].ed])        
                {        
                    stk[top
++= edge[i].ed;      
                    cur 
= edge[i].ed;        
                    pre[edge[i].ed] 
= i;                       
                    
break;     
                }        
            }     
            
if(i == -1)       
            {        
                del[cur] 
= 1;        
                top
--;        
                
if(top) cur = stk[top-1];        
            }        
        }                
        
if(cur == dest)        
        {       
            minf 
= INF;        
            
while(cur != src)        
            {        
                cur 
= pre[cur];        
                
if(edge[cur].cap - edge[cur].flow < minf) minf = edge[cur].cap - edge[cur].flow;        
                cur 
= edge[cur].st;        
            }
            cur 
= dest;        
            
while(cur != src)        
            {        
                cur 
= pre[cur];        
                edge[cur].flow 
+= minf;        
                edge[cur
^1].flow -= minf;        
                
if(edge[cur].cap - edge[cur].flow == 0)
                {
                     ptr 
= edge[cur].st;
                }
                cur 
= edge[cur].st;        
            }        
            
while(top > 0&& stk[top-1!= ptr) top--;        
            
if(top)  cur = stk[top-1];        
            ret 
+= minf;      
        }        
    }        
    
return ret;        
}        
int Dinic(int src, int dest, int ver)        
{        
    
int  ret = 0, t;        
    
while(dinic_bfs(src, dest, ver))        
    {        
        t 
= dinic_dfs(src, dest, ver);        
        
if(t) ret += t;        
        
else  break;        
    }        
    
return ret;        
}
//下面是求最短路用到的数据结构。 
struct T
{
    
int v, w, next;
}fn[MAXM];
int th, g[MAXN], dis1[MAXN], dis2[MAXN], pre[MAXN], visit[MAXN];
int map[MAXN][MAXN], cat[MAXN][MAXN];
void insert(int u, int v, int w)
{
    fn[th].v 
= v, fn[th].w = w, fn[th].next = g[u], g[u] = th++;
}
void spfa(int s, int t, int n, int * dis, int sign)
{
    
int i, j, u, v;
    th 
= 0;
    
for (i = 0; i <= n; i++)
    {
        g[i] 
= -1;
    }
    
for (i = 1; i <= n; i++)
    {
        
for (j = 1; j <= n; j++)
        {
            
if (map[i][j] < INF)
            {
                
if (sign)
                {
                    insert(i, j, map[i][j]);
                }
                
else
                {
                    insert(j, i, map[i][j]);
                }
            }
        }
    }
    
for (i = 0; i <= n; i++)
    {
        visit[i] 
= 0;
        dis[i] 
= INF;
    }
    queue
<int> que;
    dis[s] 
= 0, visit[s] = 1;
    que.push(s);
    
while (!que.empty())
    {
        u 
= que.front();
        que.pop();
        visit[u] 
= 0;
        
for (i = g[u]; i != -1; i = fn[i].next)
        {
            v 
= fn[i].v;
            
if (dis[v] > dis[u] + fn[i].w)
            {
                dis[v] 
= dis[u] + fn[i].w;
                
if (!visit[v])
                {
                    que.push(v);
                    visit[v] 
= 1;
                }
            }
        }
    }
}
void build (int s, int t, int n)
{
    
int i, j, v;
    E 
= 0;
    
for (i = 0; i <= n + 10; i++)
    {
        head[i] 
= -1;
    }
    
for (i = 1; i <= n; i++)
    {
        
for (j = g[i]; j != -1; j = fn[j].next)
        {
            v 
= fn[j].v;
            
if (dis1[i] + dis2[v] + fn[j].w == dis1[t])//对所有边满足最短路上的边建图。 
            {
                add(i, v, cat[i][v]);
            }
        }
    }
     
int ans = Dinic(s, t, n + 10);
     printf(
"%d\n", ans);
}
int main()
{
    
int t, n, m, ver, i, j, u, v, w;
    scanf(
"%d"&t);
    
while (t--)
    {
        scanf(
"%d%d"&n, &m);
        
for (i = 1; i <= n; i++)
        {
            
for (j = 1; j <= n; j++)
            {
                map[i][j] 
= INF;
                cat[i][j] 
= 0;
            }
        }

        
while (m--)
        {
            scanf(
"%d%d%d"&u, &v, &w);
            
if (u != v)
            {
                
if (map[u][v] > w)
                {
                    map[u][v] 
= w;
                    cat[u][v] 
= 1;
                }
                
else if (map[u][v] == w)
                {
                    cat[u][v]
++;//边容量++ 
                }
            }
        }
        
int s, t, flow;
        scanf(
"%d%d"&s, &t);
        spfa(t, s, n, dis2, 
0);
        spfa(s, t, n, dis1, 
1);
        build(s, t, n);
    }
    
return 0;
}
/*
2 2
1 2 1
1 2 2
1 2

2 1
1 2 1
1 2


3 2
1 2 1
2 3 4

*/