4467奇妙的方式优化暴力的01边查询

题意：
      给你n个点，每个点上只有两种颜色0,1,然后m条边每条边上都有权值，然后两种操作，第一种是询问，给你ab,(ab=00 ,11,01/10),然后问你这样的边的权值和是多少？第二种操作就是把一个点的颜色取反。


思路：
      用了将近一天去理解这个，看到网上的题解几乎都一样，感觉没说到重点怎么看也不会，最后不小心看到有哥们的博客，然后模拟几遍，有了自己的理解，首先这个题目暴力的话时间复杂度最坏是O(q*m)的，10W*10W比较大会TLE,然后就是去优化暴力的姿势，单纯暴力的话很容易想到两种方法，一个是每次更新时单纯的计算边的权值然后进行更新，另一个就是给每个点都开个变量，纪录连接他的0的总权值和连接他的1的总权值，去更新，两个时间复杂度是一样的，下面说下AC的方法，没记错应该是两种做法吧，思想大体相同，想想上面的两种暴力方法是不是要建立双向边？也就是没有收到边的方向限制，如果加上边的方向限制怎么样保证正确性？保证正确性之后怎么样保证他的速度是快的？一一解释：


deg[i] 表示i节点的度数
OI[a][b]表示和a节点相连的b颜色点的权值和


首先我们要把每个点的度数求出来，然后如果deg[a]<=deg[b]，那么建立边a->b,然后把b的相邻的a的颜色加上b的权值，也就是OI[b][Color[a]] += cost，然后每次更新的时候就是处理两个问题，一个是边相连的，这个直接暴力，然后就是计算OI[][],这个可以o1时间搞定，还有就是更新完之后在吧相邻的OI[][]更新了，查询是o1的时间复杂度，这样就完事了，这么说完肯定没听懂！
思想就是把无向边变有向，向下是暴力更新，向上是计算01的总和，时间复杂度据说是O(q*sqrt(m)) 这个用我的这个方法的话我证明不清楚，网上的那个sqrt(m)为界限的好证明，我这么实现我觉得不好证明，但是我感觉这么写会比sqrt的那个快（我自己感觉），我只能说这个方法肯定是优化的，而且可以AC。


（1）为什么建边的时候是小的度数指向大的度数，可以反过来吗？
 
：小指向大是为了把暴力的部分给边少的点来跑，反过来后会超时，这个要是能理解建边的理由的话应该很容易想到。
 
（2）怎么保证正确性？
：这个是我想了一天的地方，首先，把无向边变成有向边后会怎样？是不是通过边查找更新的时候只能更新下面的，也就是自己指向的，而没有更新指向自己的，指向自己的我们可以用另一种暴力的方法，就是记录每个点相连的0颜色和1颜色的总权值，然后可以直接算出来，每次更新的时候向上直接算，向下暴力跑，然后向下暴力跑的时候记得把下面那个点的上面更新了，这个地方非常关键，如果能理解了这就应该知道这么做的正确性以及速度快的原因，但是时间复杂度算起来...


（3）注意度数相等的时候的建边方式，可以随意指向方向，但是记住尽量别建双向边，双向边在更新的时候还要特出处理，麻烦。


（4）还有什么坑点
:a数据范围 longlong或者__ing64
:b重复边问题，记得合并重复边，不然同样的边不停出现优化会没有意义，这个要是能明白（2）应该很容易想到。
好大体就这样，这个题主要是靠自己理解，要去想这样做为什么是快的，这样做的正确性是怎么保证的，我觉得这道题必须要明白这两点，不然做了相当于没做。     

#include<map> #include<stdio.h> #include<string.h>#define N_node 100000 + 10 #define N_edge 200000 + 20using namespace std;typedef struct {int to ,next;long long cost; }STAR;typedef struct {int a ,b;long long c; }EDGE;STAR E[N_edge]; EDGE edge[N_edge]; map<long long ,long long>mark; int list[N_node] ,tot; int deg[N_node]; int Color[N_node]; long long OI[N_node][2];void add(int a, int b ,long long c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }int main () {int n ,m ,q ,a ,b ,cas = 1 ,i;long long c ,O[5];char str[10];while(~scanf("%d %d" ,&n ,&m)){for(i = 1 ;i <= n ;i ++)scanf("%d" ,&Color[i]);memset(deg ,0 ,sizeof(deg));mark.clear();int nowid = 0;O[0] = O[1] = O[2] = 0;for(i = 1 ;i <= m ;i ++){scanf("%d %d %lld" ,&a ,&b ,&c);O[Color[a]+Color[b]] += c;if(a > b) a =a + b ,b = a - b ,a = a - b;if(!mark[a*(long long)1000050 + b]){mark[a*(long long)1000050 + b] = ++nowid;edge[nowid].a = a ,edge[nowid].b = b;edge[nowid].c = c;deg[a] ++ ,deg[b] ++;}else edge[mark[a*(long long)1000050+b]].c += c;}memset(list ,0 ,sizeof(list)) ,tot = 1;memset(OI ,0 ,sizeof(OI));for(i = 1 ;i <= nowid ;i ++){a = edge[i].a ,b = edge[i].b ,c = edge[i].c;if(deg[a] < deg[b]) add(a ,b ,c) ,OI[b][Color[a]] += c;else add(b ,a ,c) ,OI[a][Color[b]] += c;}printf("Case %d:\n" ,cas ++);scanf("%d" ,&q);while(q--){scanf("%s" ,str);if(str[0] == 'A'){scanf("%d %d" ,&a ,&b);printf("%lld\n" ,O[a+b]);}else{scanf("%d" ,&a);O[Color[a]+0] -= OI[a][0];O[(Color[a]^1)+0] += OI[a][0];O[Color[a]+1] -= OI[a][1];O[(Color[a]^1)+1] += OI[a][1];for(int k = list[a] ;k ;k = E[k].next){b = E[k].to;O[Color[a]+Color[b]] -= E[k].cost;O[(Color[a]^1)+Color[b]] += E[k].cost;OI[b][Color[a]] -= E[k].cost;OI[b][Color[a]^1] += E[k].cost;}Color[a] ^= 1;}}}return 0; }

   

总结

以上是生活随笔为你收集整理的4467奇妙的方式优化暴力的01边查询的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。