N個點，M條無向邊。現在有Q組操作，一種是給 i號點增加能量，一種是詢問 i號點相鄰點的能量和(點間有多條邊就算兩次)。

據說暴力能過，但還是用這題學習了一下 點分塊 。 度數不超過 sqrt(M) 的為 "輕點"， 否則為 "重點"，"輕點"可以指向(連向)這兩種點，但"重點"只能指向(連向)"重點" 。val[i]表示i號點能量，sum[i]維護i號點所有相鄰的能量。"增加能量"時更新i號點相鄰點j的sum[j]，查詢時"輕點"暴力搜，"重點"直接O(1)返回 sum[i]即可。

修改時，"輕點"們可以修改"重點"，"重點"可以修改"重點"，"重點"的sum[]是被維護的，而"輕點"只有sqrt(M)條邊，爆搜沒問題。

ps : 似乎"重點"出度不超過 2*sqrt(M)，未證明。

1 #include <bits/stdc++.h> 2 using namespace std; 3 #define fst first 4 #define scd second 5 #define pb(x) push_back((x)) 6 #define mkp(x,y) make_pair((x),(y)) 7 #define ist(x) insert((x)) 8 typedef long long ll; 9 typedef pair<int ,int > pii; 10 typedef pair<ll ,ll > pll; 11 typedef vector< int > vi; 12 ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);} 13 ll qPow(ll a,ll b,ll mod){ ll ret=1ll;while(b){ if(b&1) ret=ret*a%mod;a=a*a%mod;b>>=1;} return ret; } 14 15 const int maxn=100100; 16 int degree[maxn]; 17 vi G[maxn]; 18 ll val[maxn]; 19 ll sum[maxn]; 20 pii bian[maxn]; 21 int bound; 22 23 void addedge(int u,int v){ 24 if(degree[u]<=bound) G[u].pb(v); 25 else if(degree[v]>bound) G[u].pb(v); 26 } 27 28 int main(){ 29 int T; 30 scanf("%d",&T); 31 while(T--) { 32 int N,M; 33 scanf("%d%d",&N,&M); 34 for(int i=1;i<=N;++i){ 35 degree[i]=0; 36 G[i].clear(); 37 val[i]=0ll; 38 sum[i]=0ll; 39 } 40 for(int i=1;i<=M;++i){ 41 int u,v; 42 scanf("%d%d",&u,&v); 43 pii tmp=mkp(u,v); 44 degree[u]++,degree[v]++; 45 bian[i]=tmp; 46 } 47 bound=sqrt(M); 48 for(int i=1;i<=M;++i) 49 { 50 int u=bian[i].fst,v=bian[i].scd; 51 addedge(u,v); 52 addedge(v,u); 53 } 54 int Q; 55 scanf("%d",&Q); 56 for(int i=0;i<Q;++i){ 57 int op; 58 scanf("%d",&op); 59 if(op){ 60 int u;scanf("%d",&u); 61 if(degree[u]>bound) printf("%I64d\n",sum[u]); 62 else{ 63 ll ans=0ll; 64 for(auto to: G[u]) { 65 ans+=val[to]; 66 } 67 printf("%I64d\n",ans); 68 } 69 } 70 else{ 71 int u,w;scanf("%d%d",&u,&w); 72 val[u]+=1ll*w; 73 for(auto to: G[u]){ 74 sum[to]+=1ll*w; 75 } 76 } 77 } 78 } 79 return 0; 80 } View Code

分攤復雜度，點分塊。

轉載于:https://www.cnblogs.com/Kiritsugu/p/9410814.html

總結

以上是生活随笔為你收集整理的HDU - 4858 项目管理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。