SGU185[Two shortest]

在无向带正权的图中找两条没有公共边的最短路，用网络流做。

先用最短路求出所有点到源点的距离，然后建立网络，其中点就是本来的那些点，边是原图中满足dis[u]+d[u][v]=dis[v]的边<u,v>，然后容量都为1。

求最大流，最大流的值小于2则无解，否者输出两条路径。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-21

DESCRIPTION:

网络流 乱做

http://acm.sgu.ru/problem.php?contest=0&problem=185

*/

#include <stdio.h>

 

const int oo=19930309;

const int MAXV=400+2;

 

int S,T;

int d[MAXV][MAXV];

int dis[MAXV];

bool inq[MAXV];

int q[MAXV];

int head,tail;

 

void SPFA()

{

     for (int i=S;i<=T;i++) dis[i]=oo;

     inq[q[head=tail=0]=S]=true;

     dis[S]=0;

     while (head<=tail)

     {

           int u;

           inq[u=q[(head++)%MAXV]]=false;

           for (int v=S;v<=T;v++)

               if (d[u][v]&&dis[v]>dis[u]+d[u][v])

               {

                  if (!inq[v])

                     inq[q[(++tail)%MAXV]=v]=true;

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

               }

     }

}

namespace sj

{

          const int oo=(~0u)>>1;

          const int MAXV=400+2;

          const int MAXE=400*400;

          typedef struct struct_edge* edge;

          struct struct_edge{int v,c;edge n,b;};

          struct_edge pool[MAXE];

          edge top;

          int S,T,V;

          edge adj[MAXV];

          int d[MAXV],dn[MAXV+1];

          void add_edge(int u,int v,int c)

          {

               top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;

               top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;

               adj[u]->b=adj[v],adj[v]->b=adj[u];

          }

          int augment(int u,int e)

          {

              if (u==T) return e;

              if (d[S]==V) return 0;

              int f=0,mind=V-1;

              for (edge i=adj[u];i;i=i->n)

                  if (i->c)

                  {

                     if (d[u]==d[i->v]+1)

                     {

                        int df=augment(i->v,e<i->c?e:i->c);

                        i->c-=df;

                        i->b->c+=df;

                        e-=df;

                        f+=df;

                        if (e==0) return f;

                     }

                     if (mind>d[i->v]) mind=d[i->v];

                  }

              if (f) return f;

              else

              {

                  if (!–dn[d[u]]) d[S]=V;

                  else dn[d[u]=mind+1]++;

                  return 0;

              }

          }

          int sap()

          {

              int f=0;

              dn[0]=V;

              while (d[S]<V) f+=augment(S,oo);

              return f;

          }

          void dfs(int u)

          {

               if (u==T) printf(“%d\n”,u);

               else

               {

                   printf(“%d “,u);

                   for (edge i=adj[u];i;i=i->n)

                       if ((!i->c)&&(!((i-pool)&1)))

                       {

                          i->c++;

                          i->b->c–;

                          dfs(i->v);

                          break;

                       }

               }

          }

}

 

int main()

{

    int n,m,x,y,l;

    scanf(“%d%d”,&n,&m),S=1,T=n;

    for (int u=S;u<=T;u++)

        for (int v=S;v<=T;v++)

            d[u][v]=oo;

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

        scanf(“%d%d%d”,&x,&y,&l),d[x][y]=d[y][x]=l;

    SPFA();

    sj::top=sj::pool;

    sj::S=S,sj::T=T,sj::V=n;

    for (int u=S;u<=T;u++)

        for (int v=S;v<=T;v++)

            if (dis[u]+d[u][v]==dis[v])

               sj::add_edge(u,v,1);

    if (sj::sap()<2) printf(“No solution\n”);

    else

    {

        sj::dfs(sj::S);

        sj::dfs(sj::S);

    }

}