ZOJ2760_How Many Shortest Path

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

给一个图，求从某个点到另一个点的最短路有多少条？所有的路都不共边。

首先从终点开始Spfa标记最短距离，然后建图。

建图的时候，如果满足两点之间的最短路只差为两点之间的边长，那么在网络流的模型中连接一条边。

最终也只需要跑最大流即可。

注意此题没有要求不能经过同一个点，所有不需要拆点，由于我们在网络流的模型中间加边的时候边容量为1，也就保证了每条边只遍历一边了。

注意，有可能两个不同点之间的距离也为0，真是深坑啊，无法直视。

召唤代码君：

#include <iostream>

#include <cstdio>

#include <cstring>

#define maxn 111

#define maxm 44444

typedef long long ll;

using namespace std;

ll inf=~0U>>;

ll to[maxm],next[maxm],c[maxm],first[maxn],edge;

ll d[maxn],tag[maxn],TAG=;

ll Q[maxm],bot,top;

ll ans,n,s,t;

ll dis[maxn][maxn],f[maxn];

bool can[maxn];

void _input()

{

    for (ll i=; i<=n; i++)

    {

        f[i]=inf,first[i]=-;

        for (ll j=; j<=n; j++) scanf("%lld",&dis[i][j]);

    }

    scanf("%lld%lld",&s,&t);

    s++,t++;

    Q[bot=top=]=t,f[t]=;

    while (bot<=top)

    {

        ll cur=Q[bot++];

        for (ll i=; i<=n; i++)

            if (dis[i][cur]>= && f[cur]+dis[i][cur]<f[i])

                f[i]=f[cur]+dis[i][cur],Q[++top]=i;

    }

}

void addedge(ll U,ll V)

{

    edge++;

    to[edge]=V,c[edge]=,next[edge]=first[U],first[U]=edge;

    edge++;

    to[edge]=U,c[edge]=,next[edge]=first[V],first[V]=edge;

}

void build_graph()

{

    edge=-;

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

        for (int j=; j<=n; j++)

            if (i!=j && dis[i][j]>= && f[i]==f[j]+dis[i][j])

                addedge(i,j);

}

bool bfs()

{

    Q[bot=top=]=t,d[t]=,tag[t]=++TAG,can[t]=false;

    while (bot<=top)

    {

        ll cur=Q[bot++];

        for (ll i=first[cur]; i!=-; i=next[i])

            if (c[i^]> && tag[to[i]]!=TAG)

            {

                tag[to[i]]=TAG,can[to[i]]=false;

                d[to[i]]=d[cur]+,Q[++top]=to[i];

                if (to[i]==s) return true;

            }

    }

    return false;

}

ll dfs(ll cur,ll num)

{

    if (cur==t) return num;

    ll tmp=num,k;

    for (ll i=first[cur]; i!=-; i=next[i])

        if (c[i]> && tag[to[i]]==TAG && d[to[i]]==d[cur]- && !can[to[i]])

        {

            k=dfs(to[i],min(num,c[i]));

            if (k) num-=k,c[i]-=k,c[i^]+=k;

            if (num==) break;

        }

    if (num) can[cur]=true;

    return tmp-num;

}

int main()

{

    inf*=inf;

    while (scanf("%lld",&n)!=EOF)

    {

        _input();

        if (s==t)

        {

            puts("inf");

            continue;

        }

        build_graph();

        for (ans=; bfs(); ) ans+=dfs(s,inf);

        printf("%lld\n",ans);

    }

    return ;

}