BestCoder #1-2 HDU 4858

本文主要是介绍BestCoder #1-2 HDU 4858，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

暴力的方法能过，但是网上有更优化的方法，

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define LL long long
#define N 100010
#define mod 1000000007
vector<int> V[N],up[N];//V记录边，up记录邻接节点，但度数自己大
int in[N];//记录节点度数
int sum[N],add[N];//add 保存更新
int main()
{//  priority_queue<int,vector<int>,greater<int> >int T;int n,m,Q;int a,b;int i,j;scanf("%d",&T);while(T--){scanf("%d %d",&n,&m);for(i=1;i<=n;i++){V[i].clear();in[i]=0;up[i].clear();sum[i]=add[i]=0;}while(m--){scanf("%d %d",&a,&b);V[a].push_back(b);V[b].push_back(a);in[b]++;in[a]++;}for(a=1;a<=n;a++)for(j=0;j<V[a].size();j++){b=V[a][j];if(in[b]>=in[a])up[a].push_back(b);}scanf("%d",&Q);int cmd,u,v;while(Q--){scanf("%d %d",&cmd,&u);if(cmd==0){scanf("%d",&v);add[u]+=v;for(i=0; i<up[u].size(); i++){j=up[u][i];sum[j]+=v;}}else{int ans=sum[u];for(i=0; i<up[u].size(); i++){j=up[u][i];if(in[j]!=in[u])ans+=add[j];}printf("%d\n",ans);}}}return 0;
}

这篇关于BestCoder #1-2 HDU 4858的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---