[bzoj4398] 福慧双修最短路二进制分组

题解：

　　考场上看的这道题，，，当时70分算法打挂了，今天才知道这个也是原题。。。。

　　首先，对于不跟1相邻的边，肯定不会经过两次，因为经过两次就回来了，除了增加路径长度之外没有任何意义。

　　但是跟1相邻的边是可能会经过2次的，因为虽然增加了路径长度，但这次回来就直接到终点了，所以完全可能重复走。

　　那么有一个很容易发现的思路是，我们可以强制某一条边是出边（即从1点出去可以走的边），其他边则为入边，这样的话就可以强制走不同的路了，但这样时间复杂度较大。考虑优化它。

　　可以发现，这样分组的本质就是要使得对于任意二元组(x, y)而言，x和y都至少要有两次被分配在不同的集合中，这样它们才可以互相搭配组成两条可能的路径。

　　为什么是两条呢？

　　对于相同的路径而言，分两个方向走一遍权值是不同的，也就是说对于这条路径：1 --- 2 --- 4 --- 3 --- 1，我既可以1 ---> 2 ---> 4 ---> 3 ---> 1,也可以1 <--- 2 <--- 4 <--- 3 <--- 1.如果只是单纯的把2,3两条边分在不同的集合当中，你根本不知道会找到哪条路径，也不知道是否这条路径刚好就是最优的那条。

　　观察到任意边的编号都是不同的，这意味这它们对应的二进制串至少有一位是不同的，所以我们可以枚举位数，按照当前位是0还是1给边分组，那么由于任意两个串对于的二进制串都至少有一位不同，因此它们一定会有一次被分在不同的集合当中。因为我们需要找到所有可能路径，所以要把当前位是0的分给s1和当前位是0的分给s2都试一遍才能保证正确性。

　　但实际上你会发现不用试2遍也可以过这道题，这是数据原因，，，因为我已经把我原来那份代码给hack掉了。。。。

　　因为你可以发现，会发生错误的几率是很低的，因为发生错误当且仅当对应的最短路径没有被找到，而这种情况出现在1号点对应的出边和入边的编号刚好所有不同的地方都是1 对 0或者0 对1，并且刚好那个1 对 0(0对1)就会将2条边分在错误的集合。

　　所以除非构造数据来卡，不然出现错误的可能性是很低的。

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define LL long long

 #define AC 50100

 #define ac 401000

 int n, m, t, ans = INT_MAX, k;

 int dis[AC], s[ac], top;

 int Head[AC], date[ac], Next[ac], len[ac], tot = ;

 bool vis[AC];

 struct road{

     int x, y, dis1, dis2;

 }way[ac];

 struct node{

     int dis, id;

 };

 struct cmp{

     bool operator () (node a, node b)

     {

         return a.dis > b.dis;

     }

 };

 priority_queue<node, vector<node>, cmp> q;

 inline int read()

 {

     int x = ;char c = getchar();bool z = false;

     while(c > '' || c < '')

     {

         if(c == '-') z = true;

         c = getchar();

     }

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     if(!z) return x;

     else return -x;

 }

 inline void upmin(int &a, int b)

 {

     if(b < a) a = b;

 }

 inline void upmax(int &a, int b)

 {

     if(b > a) a = b;

 }

 inline void add(int f, int w, int S)

 {

     if(w == ) w = t;

     date[++tot] = w, Next[tot] = Head[f], Head[f] = tot, len[tot] = S;

     //printf("%d ---> %d : %d\n", f, w, S);

 }

 void pre()

 {

     n = read(), m = read(), t = n + ;

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

     {

         way[i].x = read(), way[i].y = read(), way[i].dis1 = read(), way[i].dis2 = read();

         if(way[i].x ==  || way[i].y == ) s[++top] = i;

     }

 }

 void build(int x)

 {

     //printf("%d:\n", x);

     int l = ;

     tot = ;

     memset(Head, , sizeof(Head));

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

     {

         if(i == s[l])

         {

             if(k ^ (l & x))//不仅仅要被分在不同集合当中，

             {//还需要x1s1 + x2s2 ; x1s2 + x2x1两种情况都出现一次才能包括所有的情况

                 if(way[i].x == ) add(way[i].x, way[i].y, way[i].dis1);

                 else add(way[i].y, way[i].x, way[i].dis2);

             }

             else

             {

                 if(way[i].x == ) add(way[i].y, way[i].x, way[i].dis2);

                 else add(way[i].x, way[i].y, way[i].dis1);

             }

             l ++;

         }

         else

         {

             add(way[i].x, way[i].y, way[i].dis1);

             add(way[i].y, way[i].x, way[i].dis2);

         }

     }

 }

 void spfa()

 {

     int x, now;

     memset(dis, , sizeof(dis));

     memset(vis, , sizeof(vis));

     dis[] = ;

     q.push((node){, });

     while(!q.empty())

     {

         x = q.top().id, q.pop();

         while(vis[x] && !q.empty()) x = q.top().id, q.pop();

         if(vis[x]) break;

         vis[x] = true;

         for(R i = Head[x]; i; i = Next[i])

         {

             now = date[i];

             if(dis[now] > dis[x] + len[i])

             {

                 dis[now] = dis[x] + len[i];

                 q.push((node){dis[now], now});

             }

         }

     }

     upmin(ans, dis[t]);

 }

 void work()

 {

     int tmp = ;

     for(R i = ; i <= ; i ++)

     {

         k = , build(tmp), spfa();

         k = , build(tmp), spfa();

         tmp <<= ;

     }

     printf("%d\n", ans);

 }

 int main()

 {

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

     pre();

     work();

     fclose(stdin);

     return ;

 }

巴特西

[bzoj4398] 福慧双修最短路二进制分组

最新文章

热门文章

巴特西

[bzoj4398] 福慧双修 最短路 二进制分组

最新文章

热门文章

[bzoj4398] 福慧双修最短路二进制分组