Gym 100917F Find the Length

题目链接:http://codeforces.com/gym/100917/problem/F

------------------------------------------------------------------------------------------------

给出一个无向正权无自环图要求对于每个点经过它的最短"简单环"的长度

其中简单环的定义是环上每条无向边都经过且仅经过一次

显然这个环至少经过三条边三个点

我们或许会产生这样一种思路对于每次询问我们以该点$s$作为起点

先处理出到其余每点的最短路然后枚举一条边两端分别为$u\ v$

用$s$分别到$u\ v$的最短路再加上这条边的长度来更新结果

然而这样连样例都过不了因为会产生重边

于是我们考虑把最短路径所经过的边都标记一下(多个可选的话随便标记一个)

然后枚举边的时候碰到标记过的边就直接跳过

不过这样还存在一种情况就是 $u\ v$ 属于最短路径边所构成树上的除根节点外同一子树

这种情况也是会有重边的所以这里再判断以下去除就好

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 const int N = , E = N * N * ;

 int firste[N], nexte[E], v[E], w[E], flag[E];

 int used[N], dist[N], fa[N];

 int n, e = ;

 void build(int x, int y, int z)

 {

     nexte[++e] = firste[x];

     firste[x] = e;

     v[e] = y;

     w[e] = z;

 }

 int main()

 {

     scanf("%d", &n);

     int x;

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

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

         {

             scanf("%d", &x);

             if(i >= j)

                 continue;

             if(x != -)

             {

                 build(i, j, x);

                 build(j, i, x);

             }

         }

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

     {

         int u = i;

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

             fa[j] = j;

         memset(dist, 0x3f, sizeof dist);

         dist[u] = ;

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

         {

             used[u] = i;

             int mdist = 1e9, tu;

             for(int p = firste[u]; p; p = nexte[p])

                 if(dist[v[p]] > dist[u] + w[p])

                     dist[v[p]] = dist[u] + w[p];

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

                 if(used[j] != i && dist[j] < mdist)

                 {

                     tu = j;

                     mdist = dist[j];

                 }

             for(int p = firste[tu]; p; p = nexte[p])

                 if(dist[tu] == dist[v[p]] + w[p])

                 {

                     flag[p] = flag[p ^ ] = i;

                     if(v[p] != i)

                         fa[tu] = fa[v[p]];

                     break;

                 }

             u = tu;

         }

         int ans = 1e9;

         for(int p = ; p < e; p +=)

             if(flag[p] != i && fa[v[p]] != fa[v[p ^ ]])

                 ans = min(ans, dist[v[p]] + dist[v[p ^ ]] + w[p]);

         printf("%d\n", ans < 1e9 ? ans : -);

     }

     return ;

 }

巴特西

Gym 100917F Find the Length

最新文章

热门文章