本文主要是介绍HDU-4467-Graph（莫队思想），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4467
题意：给你n个点，m条边，每条边有一个权值，有两个操作，一个是修改单点的颜色（颜色只有0,1两种），一个是询问边的两个端点都为指定颜色的权值和。
思路：由于每个点的颜色只有0，1两种，那么答案只有3种情况（00,01,11），用一个数组维护即可。即ans[0]统计边的两端都是0的权值和，ans[1]统计边的两端为1和0的权值总和，ans[2]统计边的两端都是1的权值和。根据莫队的思想，我们根据度数将点分为轻重点，这样我们对轻点进行暴力维护，重点就维护周围的权值。注意重边的处理。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+7;
struct node
{int st;ll w0,w1;
} p[maxn];
struct edge
{ll u,v;ll w;
} e[maxn],ed;
int color[maxn],deg[maxn];
ll ans[3];
bool cmp(edge x,edge y)
{if (x.u>y.u) return true;else return false;
}
int main()
{int n,m,i,Case;ll u,v,w;char s[10];Case = 1;while (scanf("%d%d",&n,&m)!=EOF){memset(deg,0,sizeof(deg));for (i = 1; i <= n; i++) scanf("%d",&color[i]);map<pair<ll,ll>, ll> r;for (i = 1; i <= m; i++){scanf("%lld %lld %lld",&u,&v,&w);if(u > v) swap(u,v);r[{u,v}] += w;}m = 0;for(auto it: r)e[++m].u = it.first.first, e[m].v = it.first.second, e[m].w = it.second;ans[0] = ans[1] = ans[2] = 0;for (i = 1; i <= m; i++){u = e[i].u; v = e[i].v;deg[u]++; deg[v]++; //记录度数if (color[u]!=color[v]) ans[2] += e[i].w;else ans[color[u]] += e[i].w; //初始化三种情况的权值和}for (i = 1; i <= m; i++){u = e[i].u; v = e[i].v;if (deg[u] > deg[v])swap(e[i].u,e[i].v);}sort(e+1, e+m+1, cmp); //使u的度数小于v的度数，并排序，这样可以直接逐边处理memset(p,0,sizeof(p));for (i = 1; i <= m; i++){u = e[i].u; v = e[i].v;if (p[u].st == 0) p[u].st = i; //记录u节点第一次出现的位置if (color[u]) p[v].w1 += e[i].w;else p[v].w0 += e[i].w; //存储点的w0和w1}int q;scanf("%d",&q);printf("Case %d:\n",Case++);while (q--){int x,y;scanf("%s",s);if (s[0] == 'A'){scanf("%d%d",&x,&y);if (x != y) printf("%lld\n",ans[2]);else printf("%lld\n",ans[x]);}else{scanf("%d",&x);if (color[x]){ans[2] += p[x].w1;ans[2] -= p[x].w0;ans[0] += p[x].w0;ans[1] -= p[x].w1;}else{ans[2] -= p[x].w1;ans[2] += p[x].w0;ans[0] -= p[x].w0;ans[1] += p[x].w1;}color[x] = 1 - color[x];int st = p[x].st;while (st <= m && e[st].u == x){v = e[st].v;if (color[x] != color[v]){ans[2] += e[st].w;ans[1-color[x]] -= e[st].w;}else{ans[color[x]] += e[st].w;ans[2] -= e[st].w;}if (color[x] == 0){p[v].w0 += e[st].w;p[v].w1 -= e[st].w;}else{p[v].w0 -= e[st].w;p[v].w1 += e[st].w;}st++;}}}}return 0;
}
这篇关于HDU-4467-Graph（莫队思想）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
