首页 > 代码库 > HDU 4858 - 项目管理 - 图的分块
HDU 4858 - 项目管理 - 图的分块
项目管理
给一个n(不超过10^5)个点，m(不超过n+10)条边的点带权图，有两种操作：1、将某点权值增加；2、询问与某点直接相连的点的权值和。操作次数范围题目没有给出。
【图的分块】称度大于sqrt(n)的点为重点，其余为轻点。由于度数最多为2*m，所以重点不超过2*sqrt(n)个。先算sum[]，sum[i]表示与点i相连的轻点的权值和。
对操作1，如果它是轻点，直接O(sqrt(n))更改所有与其相连的点的sum[]，如果是重点，那么O(1)更改其点权即可。
对操作2，与其相连的轻点权值和为sum[]，然后再O(sqrt(n))访问所有与其相连的重点（这里需要预处理求出每个点的重点）求权值和。总的来说，每个操作复杂度都是sqrt(n)。
From here
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<set>#include<map>#include<stack>#include<vector>#include<queue>#include<string>#include<sstream>#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define clr(i,j) memset(i,j,sizeof(i))#define MAXN 100005#define MAXM 300005#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,big,cas,num;bool flag;int edge,deg[MAXN],sum[MAXN],w,q,u,v,value[MAXN];vector <int> G[MAXN],HG[MAXN];int main(){ scanf("%d",&T); while (T--) { clr(deg,0); clr(sum,0); clr(value,0); edge=0; scanf("%d%d",&n,&m); for (i=1;i<=n;i++) G[i].clear(); for (i=1;i<=m;i++)//使用邻接表读入 { scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); deg[x]++;deg[y]++; } int d=(int)(sqrt(n)+eps); for (i=1;i<=n;i++)//预处理与每个点相邻的重点列表 { HG[i].clear(); for (j=0;j<G[i].size();j++) { if ( deg[ G[i][j] ] > d ) HG[i].push_back(G[i][j]); } } scanf("%d",&q); for (i=1;i<=q;i++) { int ch; scanf("%d",&ch); if (ch==0) { scanf("%d%d",&u,&w); if (deg[u]<=d)//轻点 { for (j=0;j<G[u].size();j++) { sum[ G[u][j] ]+=w; } }else//重点 { value[u]+=w; } }else { scanf("%d",&u); ans=sum[u];//这是周围轻点的权值和 for (j=0;j<HG[u].size();j++)//再枚举每个重点的权值，累加 { ans+=value[ HG[u][j] ]; } printf("%d\n",ans); } } }}
HDU 4858 - 项目管理 - 图的分块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。