Q - Marriage Match IV

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

题意：一个人从城市 A 到 B 的最短路径有几条，这里特别需要注意：每条路经只能走一次，走过之后就不能再走了，而且只能走最短的路径
思路：把不是最组成短路径（这里最短路可能有多条）点边剔除掉，把剩余的边重新建图，边权设置为1，跑一遍最大流。

那么我们我现在要解决的问题是怎么判断某一条边是组成最短路径的边呢？

我们先做一些假设：

假设要判断的边是（u ，v），其长度是 w（u，v），假设图的源点为 s 、汇点为 e。
正向跑最短路的到的从 s 到其他点的最短距离存放在 dis1[ ] 数组中，

dis[ u ] 为s到u的最短距离；
逆向跑最短路（但是带到权值还是正向的权值）的到的从 e 到其他点的最短距离存放在 dis2[ ] 数组中，dis[ v ] 为u到e (注意这个方向是u到v)的最短距离

最后我们只要在遍历所给的每一条边时：

如果 dis1[ u ] + w(u, v) + dis2[ v ] = dis1[ e ] 成立。那么我们就可判断这条边就是组成最短的路径的边。

最后把这些边新建图跑最大流，就能得出路径方案数了。
其实剩下的我们还要考虑一下：为什么最大流跑出来的就是我们所要的答案？？？？？？？？？

题解（Spfa + ISAP）

#include<iostream>

#include<queue>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define INF 0x3f3f3f3f

const int maxn = 10005;

const int maxm = 200005;

struct Edge

{

    int v,w,next;

} edge1[maxm], edge2[maxm], edge[maxm];

int n,m,s,e;

int head1[maxn], head2[maxn], head[maxn];

int dis1[maxn], dis2[maxn];

int use[maxn];

int k1,k2,k;

void Add(int u, int v, int w, int head[], int & k, Edge edge[])

{

    edge[++ k] = (Edge){ v, w, head[u]}; head[u] = k;

}

void Spfa(int s, int dis[], int head[], Edge edge[])

{

    for(int i = 1; i <= n; i ++)

        dis[i] = INF,use[i] = 0;

    dis[s] = 0;

    queue<int> q;

    q.push(s);

    int u,v,w;

    while(! q.empty())

    {

        u = q.front();

        q.pop();

        use[u] = 0;

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

        {

            v = edge[i].v;

            w = edge[i].w;

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

            {

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

                if(! use[v])

                {

                    q.push(v);

                    use[v] = 1;

                }

            }

        }

    }

}

int deep[maxn], num[maxn];

int cur[maxn], last[maxm];

void bfs(int e)

{

    for(int i = 0; i <= n; i ++)

        deep[i] = n, cur[i] = head[i], use[i] = 0;

    deep[e] = 0;

    queue<int> q;

    q.push(e);

    int u, v;

    while(! q.empty())

    {

        u = q.front(); q.pop();

  //      use[u] = 0;

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

        {

            v = edge[i].v;

            if(edge[i^1].w && deep[v] == n)      //正图 边存在 且 v这个节点没有被求过

            {

                deep[v] = deep[u] + 1;

                    q.push(v);

//                if(! use[v])

//                {

//                    q.push(v);

//                    use[v] = 1;

//                }

            }

        }

    }

}

int Add_flow(int s, int e)

{

    int ans = INF;

    int now = e;

    while(now != s)

    {

        ans = min(ans, edge[last[now]].w);

        now = edge[last[now]^1].v;

    }

    now = e;

    while(now != s)

    {

        edge[last[now]].w -= ans;

        edge[last[now]^1].w += ans;

        now = edge[last[now]^1].v;

    }

    return ans;

}

int isap(int s, int e)

{

    int now = s;    //从起点开始进行操作

    bfs(e);         //先找出来一条边 被操作的增光路

    for(int i = 1; i <= n; i ++) num[deep[i]] ++;

    int mx_flw = 0;

    while(deep[s] < n)

    {

        if(now == e)        //如果到达汇点直接增广，重新回到源点进行下一轮增广

        {

            mx_flw += Add_flow(s, e);

            now = s;

        }

        bool has_find = 0;

        for(int i = cur[now]; i != -1; i = edge[i].next)

        {

            if(edge[i].w && deep[now] == deep[edge[i].v] + 1)

            {

                has_find = 1;   //做标记已经找到一种可行路径

                cur[now] = i;     //优化当前弧

                now = edge[i].v;

                last[edge[i].v] = i;

                break;

            }

        }

        if(! has_find)

        {

            int minn = n - 1;

            for(int i = head[now]; i != -1; i = edge[i].next)

                if(edge[i].w)

                    minn = min(minn, deep[edge[i].v]);

            if( (-- num[deep[now]]) == 0) break;   //gap 优化出现了断层

            num[deep[now] = minn + 1] ++;

            cur[now] = head[now];

            if(now != s)

                now = edge[last[now]^1].v;

        }

    }

    return mx_flw;

}

void init()

{

    k1 = 0; k2 = 0; k = -1;

    for(int i = 0; i <= n; i ++)

        head1[i] = -1, head2[i] = -1, head[i] = -1;

    memset(num, 0, sizeof(num));

}

int main()

{

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

    int t;

    scanf("%d", &t);

    while(t --)

    {

        scanf("%d %d", &n, &m);

        init();

        int u, v, w;

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

        {

            scanf("%d %d %d", &u, &v, &w);

            Add(u, v, w, head1, k1, edge1);

            Add(v, u, w, head2, k2, edge2);

        }

        scanf("%d %d", &s, &e);

        Spfa(s, dis1, head1, edge1);

        Spfa(e, dis2, head2, edge2);

        //遍历图中所有的边 去找组成所有最短了的边都有哪些

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

        {

            u = edge2[i].v;

            v = edge1[i].v;

            w = edge1[i].w;

            if(dis1[u] + w + dis2[v] == dis1[e])

            {

                Add(u, v, 1, head, k, edge);

                Add(v, u, 0, head, k, edge);

            }

        }

        printf("%d\n", isap(s, e));

    }

    reurn 0;

}

巴特西

Q - Marriage Match IV (非重复最短路 + Spfa + 网络最大流Isap)

Q - Marriage Match IV

题解（Spfa + ISAP）

最新文章

热门文章