SGU185 - Two Shortest

原题地址：http://acm.sgu.ru/problem.php?contest=0&problem=185

题目大意：给出一个无向图，求出从 1 到 n 的两条没有相同边的最短路径（允许有重复点），要求输出具体路径，不存在则输出"No solution"。保证两点之间没有重边。

数据范围和限制：点数 2 <= N <= 400, 边长小于等于10000。时间限制 0.25s 内存限制 4M

题目分析：

这题应该算是经典题目了，半年之前第一遍写就没过，昨天复习图论时下定决心开始搞定这道题，结果无限WA，刚刚总算把它调对了。话说SGU我还没做过几道题呢（惭愧）……

题目首先要求最短路，而且两条路必须都是最短路，而不能是一条最短的和一条次短的。那我们不妨先求出从 1 出发的单源最短路，然后考察最短路中的最优子结构性质：即若从 1 到 i 的最短路上经过了点 j ，则必须要满足 dist[j] + map[j][i] == dist[i]，否则我们总能找到一条更短的路径。这样我们不妨直接把不满足以上性质的边全部删除就好了。

下一个要求是不能有重复边。我们可以以 1 为源点， n 为汇点，剩下所有边的容量设为 1，做一遍最大流，如果最大流大于等于 2则有可行解，写一个DFS输出流的路径就行了，否则说明无重叠最短路不存在，输出无解信息

 //date 20140115

 #include <cstdio>

 #include <cstring>

 const int maxn = ;

 const int maxm = ;

 const int INF = 0x7F7F7F7F;

 inline int getint()

 {

     int ans(); char w = getchar();

     while('' > w || '' < w)w = getchar();

     while('' <= w && w <= '')

     {

         ans = ans *  + w - '';

         w = getchar();

     }

     return ans;

 }

 inline int min(int a, int b){return a < b ? a : b;}

 int n, m;

 int map[maxn][maxn];

 struct edge

 {

     int u, v, c, next;

 }E[maxm];

 int a[maxn];

 int nedge;

 inline void add(int u, int v, int c)

 {

     E[++nedge].u = u;

     E[nedge].v = v;

     E[nedge].c = c;

     E[nedge].next = a[u];

     a[u] = nedge;

 }

 int dis[maxn];

 inline void init()

 {

     static int q[maxn];

     static int inQ[maxn];

     memset(dis, 0x7F, sizeof dis);

     memset(inQ, , sizeof inQ);

     dis[] = ;

     int l = , r = ; q[] = ; inQ[] = ;

     while(l < r)

     {

         int x = q[(++l) % maxn];

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

             if(map[x][i] >  && map[x][i] + dis[x] < dis[i])

             {

                 dis[i] = map[x][i] + dis[x];

                 if(!inQ[i]){q[(++r) % maxn] = i; inQ[i] = ;}

             }

         inQ[x] = ;

     }

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

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

             if((map[i][j] > ) && (dis[i] + map[i][j] > dis[j]))map[i][j] = ;

     nedge = ;

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

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

             if(map[i][j] > )

             {

                 add(i, j, );

                 add(j, i, );

             }

 }

 int now[maxn];

 int lab[maxn];

 inline int label()

 {

     static int q[maxn];

     int l = , r = ;

     memset(lab, 0xFF, sizeof lab);

     q[] = ; lab[] = ;

     while(l < r)

     {

         int x = q[++l];

         for(int i = a[x]; i; i = E[i].next)

             if(E[i].c >  && lab[E[i].v] == -)

             {

                 lab[E[i].v] = lab[x] + ;

                 q[++r] = E[i].v;

 //                now[x] = i;

             }

     }

     return (lab[n] != -);

 }

 inline int Dinic(int v, int f)

 {

     if(v == n)return f;

     int w, res = ;

     for(int i = now[v]; i; i = now[v] = E[i].next)

         if((E[i].c > ) && (f > ) && (lab[v] +  == lab[E[i].v]) && (w = Dinic(E[i].v, min(f, E[i].c))))

         {

             E[i].c -= w;

             E[i ^ ].c += w;

             f -= w;

             res += w;

         }

     return res;

 }

 inline int max_flow()

 {

     int ans = ;

     for(int i = ; i <= n; ++i)now[i] = a[i];

     while(label()){ans += Dinic(, INF);for(int i = ; i <= n; ++i)now[i] = a[i];}

     return ans;

 }

 void dfs(int v)

 {

     if(v == n)printf("%d\n", v);

     for(int i = a[v]; i; i = E[i].next)if(E[i].c ==  && map[v][E[i].v] >  && dis[v] + map[v][E[i].v] == dis[E[i].v])

     {

         printf("%d ", v); dfs(E[i].v); map[v][E[i].v] = ; return;

     }

 }

 inline void output()

 {

     dfs(), dfs();

 }

 int main()

 {

     freopen("sgu185.in", "r", stdin);

     freopen("sgu185.out", "w", stdout);

     n = getint(); m = getint();

     memset(map, , sizeof map);

     memset(a, , sizeof a);

     memset(E, , sizeof E);

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

     {

         int x, y, z;

         x = getint(); y = getint(); z = getint();

         map[x][y] = map[y][x] = z;

     }

     init();

     int ans = max_flow();

     if(ans < )printf("No solution\n");

     else output();

     return ;

 }

代码说明：求最短路的时候我用的SPFA，使用邻接矩阵存储，删边之后重新建图使用邻接表，用Dinic求最大流最后DFS递归输出答案就行

一些心得和收获：昨天第一遍写的时候用了两个邻接表，但是SPFA忘记开滚动队列了，由于机房关门了回家之后也没细查。今早到学校之后重写了一遍Dijkstra版本的，但是Dijkstra好像写错了无限WA……之后该做SPFA（但还是邻接矩阵）终于查出没有滚动队列的问题，之后开始TLE on test33，才发现Dinic的当前弧优化没写好，后来改对了总算AC了，我也总算有了自己比较熟练的最大流模板了。今天一上来邻接表的范围算错了，算成了400 * 400 * 2(网络流反向边)，结果被SGU内存限制卡的死死的，后来证明出最短路删边之后图就变成单向的了没必要 * 2。继续加油！

巴特西

SGU185 - Two Shortest

最新文章

热门文章