不相交最短路径数目

Source

HDU3416

题意:
有n个城市,m条边,a到b耗费为c,为单向边。要求从s到t的最短路径有多少条,每一条边只能走一次。
思路:把每条最短路经过的边加到网络流的图中,跑一个最大流就是条数,因为不相交,则边容量为1.

#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>
#define pi pair<int,int>
#define mak(a,b) make_pair(a,b)
const int N=1000+5;
const int M=1e5+5;
const int INF=0x3f3f3f3f;
using namespace std;
struct Edge{int to,len,nex;}edge1[M],edge2[M*2];//分别为原图和网络流图里的边
int a[M],b[M],z[M];
int head1[N],head2[N],d1[N],d2[N];
int tot,n,m,s,t;
bool vis[N];
void add(int from,int to,int len,bool flag)
{
   if(flag)
   {
       edge2[++tot]=(Edge){to,len,head2[from]};head2[from]=tot;
       edge2[++tot]=(Edge){from,0,head2[to]};head2[to]=tot;
   }
   if(!flag)
       edge1[++tot]=(Edge){to,len,head1[from]};head1[from]=tot;
}
priority_queue<pi,vector<pi>,greater<pi> >Q;
void dijkstra(int t)
{
    while(!Q.empty())
        Q.pop();
    for(int i=1;i<=n;i++)
        d2[i]=INF;
    Q.push(mak(0,t));
    d2[t]=0;
    while(!Q.empty())
    {
        int x=Q.top().second;
        Q.pop();
        for(int i=head1[x];i;i=edge1[i].nex)
        {
            int y=edge1[i].to,l=edge1[i].len;
            if(d2[y]>d2[x]+l)
            {
                d2[y]=d2[x]+l;
                Q.push(mak(d2[y],y));
            }
        }
    }
}
void findpath(int x)
{
    vis[x]=1;
    if(x==t)
        return;
    for(int i=head1[x];i;i=edge1[i].nex)
    {
        int y=edge1[i].to,l=edge1[i].len;
        if(d1[x]+l+d2[y]==d2[s])   //d1[x]存从s到x的最短距离,d2[x]存从x到t的最短距离
        {
            d1[y]=d1[x]+l;         //保存d1[y]
            add(x,y,1,1);
            if(!vis[y])
                findpath(y);
        }
    }
}
queue<int>q;
bool bfs()
{
    for(int i=1;i<=n;i++)
        d1[i]=0;
    while(!q.empty())
        q.pop();
    q.push(s);
    d1[s]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head2[x];i;i=edge2[i].nex)
        {
            int y=edge2[i].to,l=edge2[i].len;
            if(!d1[y]&&l)
            {
                q.push(y);
                d1[y]=d1[x]+1;
                if(y==t)
                    return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)
        return flow;
    int res=flow,k;
    for(int i=head2[x];i&&res;i=edge2[i].nex)
    {
        int y=edge2[i].to,l=edge2[i].len;
        if(l&&d1[y]==d1[x]+1)
        {
            k=dinic(y,min(res,l));
            if(!k)
                d1[y]=0;
            edge2[i].len-=k;
            edge2[i^1].len+=k;
            res-=k;
        }
    }
    return flow-res;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        tot=0;
        for(int i=1;i<=n;i++)
            head1[i]=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a[i],&b[i],&z[i]);
            add(b[i],a[i],z[i],0);      //建反向边 求出各点到t的距离
        }
        scanf("%d%d",&s,&t);
        dijkstra(t);
        tot=0;//重复使用edge数组因为dijkstra已经得到d[i]那个图的边无效可被替代了
        for(int i=1;i<=n;i++)
            head1[i]=0,vis[i]=0,head2[i]=0;//head1[]建立正向边时重复使用,vis[]findpath剪枝使用,head2[]网络流建图
        for(int i=1;i<=m;i++)
            add(a[i],b[i],z[i],0);
        tot=1;//网络流tot从1开始 因为要从非零偶数开始(2);
        d1[s]=0;
        findpath(s);
        int maxflow=0;
        while(bfs())
            maxflow+=dinic(s,INF);
        printf("%d\n",maxflow);
    }
}