Graph
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2618 Accepted Submission(s): 425
Problem Description
P. T. Tigris is a student currently studying graph theory. One day, when he was studying hard, GS appeared around the corner shyly and came up with a problem:Given a graph with n nodes and m undirected weighted edges, every node having one of two colors, namely black (denoted as 0) and white (denoted as 1), you’re to maintain q operations of either kind:* Change x: Change the color of xth node. A black node should be changed into white one and vice versa.* Asksum A B: Find the sum of weight of those edges whose two end points are in color A and B respectively. A and B can be either 0 or 1.P. T. Tigris doesn’t know how to solve this problem, so he turns to you for help.Input
There are several test cases.For each test case, the first line contains two integers, n and m (1 ≤ n,m ≤ 105), where n is the number of nodes and m is the number of edges.The second line consists of n integers, the ith of which represents the color of the ith node: 0 for black and 1 for white.The following m lines represent edges. Each line has three integer u, v and w, indicating there is an edge of weight w (1 ≤ w ≤ 231 - 1) between u and v (u != v).The next line contains only one integer q (1 ≤ q ≤ 105), the number of operations.Each of the following q lines describes an operation mentioned before.Input is terminated by EOF.Output
For each test case, output several lines.The first line contains “Case X:”, where X is the test case number (starting from 1).And then, for each “Asksum” query, output one line containing the desired answer.Sample Input
4 3
0 0 0 0
1 2 1
2 3 2
3 4 3
4
Asksum 0 0
Change 2
Asksum 0 0
Asksum 0 1
4 3
0 1 0 0
1 2 1
2 3 2
3 4 3
4
Asksum 0 0
Change 3
Asksum 0 0
Asksum 0 1
Sample Output
Case 1:
6
3
3
Case 2:
3
0
4
Source
解题:由于数量巨大,我们可以只维护部分结点的信息,其余的结点信息暴力计算就是了。
维护每个节点的sum[u][0] sum[u][1]表示与该结点相邻且是0 的sum 是1的sum
1 #include2 using namespace std; 3 typedef long long LL; 4 #define pii pair 5 const int maxn = 200010; 6 struct arc { 7 int u,v; 8 LL w; 9 bool operator<(const arc &rhs)const {10 return (u < rhs.u || u == rhs.u && v < rhs.v);11 }12 } e[500010];13 LL ans[3],sum[maxn][2];14 vector g[maxn];15 int n,m,du[maxn],color[maxn];16 bool key[maxn];17 void init() {18 memset(key,false,sizeof key);19 memset(ans,0,sizeof ans);20 memset(sum,0,sizeof sum);21 memset(du,0,sizeof du);22 for(int i = 0; i < maxn; ++i) g[i].clear();23 }24 void update(int u) {25 if(key[u]) {26 for(int i = g[u].size()-1; i >= 0; --i) {27 sum[g[u][i].first][color[u]] -= g[u][i].second;28 sum[g[u][i].first][color[u]^1] += g[u][i].second;29 }30 } else {31 sum[u][0] = sum[u][1] = 0;32 for(int i = g[u].size()-1; i >= 0; --i) {33 sum[u][color[g[u][i].first]] += g[u][i].second;34 if(key[g[u][i].first]) {35 sum[g[u][i].first][color[u]] -= g[u][i].second;36 sum[g[u][i].first][color[u]^1] += g[u][i].second;37 }38 }39 }40 ans[color[u]] -= sum[u][0];41 ans[color[u] + 1] -= sum[u][1];42 ans[color[u]^1] += sum[u][0];43 ans[(color[u]^1) + 1] += sum[u][1];44 color[u] ^= 1;45 }46 int main() {47 int cs = 1,u,v,q;48 while(~scanf("%d%d",&n,&m)) {49 printf("Case %d:\n", cs++);50 init();51 for(int i = 1; i <= n; ++i)52 scanf("%d",color + i);53 int bound = round(sqrt(n));54 for(int i = 0; i < m; ++i) {55 scanf("%d%d%I64d",&e[i].u,&e[i].v,&e[i].w);56 if(e[i].u > e[i].v) swap(e[i].u,e[i].v);57 }58 sort(e,e + m);59 int t = 1;60 for(int i = 1; i < m; ++i) {61 if(e[i].u != e[t-1].u || e[i].v != e[t-1].v) e[t++] = e[i];62 else e[t-1].w += e[i].w;63 }64 m = t;65 for(int i = 0; i < m; ++i) {66 u = e[i].u;67 v = e[i].v;68 ans[color[u] + color[v]] += e[i].w;69 if(++du[u] > bound) key[u] = true;70 if(++du[v] > bound) key[v] = true;71 }72 for(int i = 0; i < m; ++i) {73 u = e[i].u;74 v = e[i].v;75 sum[u][color[v]] += e[i].w;76 sum[v][color[u]] += e[i].w;77 if(key[u] && key[v]) {78 g[u].push_back(pii(v,e[i].w));79 g[v].push_back(pii(u,e[i].w));80 }81 if(!key[u]) g[u].push_back(pii(v,e[i].w));82 if(!key[v]) g[v].push_back(pii(u,e[i].w));83 }84 char cmd[20];85 scanf("%d",&q);86 while(q--) {87 scanf("%s",cmd);88 if(cmd[0] == 'A') {89 scanf("%d%d",&u,&v);90 printf("%I64d\n",ans[u + v]);91 } else {92 scanf("%d",&u);93 update(u);94 }95 }96 }97 return 0;98 }