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

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

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

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

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

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

 

 

召唤代码君：

 

 

 

#include 
     
      #include 
      
       #include 
       
        #define maxn 111#define maxm 44444typedef long long ll;using namespace std;ll inf=~0U>>2;ll to[maxm],next[maxm],c[maxm],first[maxn],edge;ll d[maxn],tag[maxn],TAG=520;ll Q[maxm],bot,top;ll ans,n,s,t;ll dis[maxn][maxn],f[maxn];bool can[maxn];void _input(){    for (ll i=1; i<=n; i++)    {        f[i]=inf,first[i]=-1;        for (ll j=1; j<=n; j++) scanf("%lld",&dis[i][j]);    }    scanf("%lld%lld",&s,&t);    s++,t++;    Q[bot=top=1]=t,f[t]=0;    while (bot<=top)    {        ll cur=Q[bot++];        for (ll i=1; i<=n; i++)            if (dis[i][cur]>=0 && f[cur]+dis[i][cur]
        
         =0 && f[i]==f[j]+dis[i][j])                addedge(i,j);}bool bfs(){    Q[bot=top=1]=t,d[t]=0,tag[t]=++TAG,can[t]=false;    while (bot<=top)    {        ll cur=Q[bot++];        for (ll i=first[cur]; i!=-1; i=next[i])            if (c[i^1]>0 && tag[to[i]]!=TAG)            {                tag[to[i]]=TAG,can[to[i]]=false;                d[to[i]]=d[cur]+1,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!=-1; i=next[i])        if (c[i]>0 && tag[to[i]]==TAG && d[to[i]]==d[cur]-1 && !can[to[i]])        {            k=dfs(to[i],min(num,c[i]));            if (k) num-=k,c[i]-=k,c[i^1]+=k;            if (num==0) 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=0; bfs(); ) ans+=dfs(s,inf);        printf("%lld\n",ans);    }    return 0;}