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

 

Author

starvae@HDU

 

Source

HDOJ Monthly Contest – 2010.06.05

题意：

给出一张无向图，要求图上的不相交得最短路条数。

思路：

先求出单源最短路，从终点往起点倒着搜出最短路上的边（能够用双向链表）。然后另这些边的容量为1建新图。跑一遍最大流就可以。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

#define N 1010
#define M 101000
const 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<int> 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<int> 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;
}