hdu 4858 프로젝트 관리 (그림 의 분할)

프로젝트 관리
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 252 Accepted Submission(s): 88
Problem Description
우 리 는 큰 프로젝트 를 만 들 었 다!이 항목 은 n 개의 노드 가 있 고 여러 변 으로 연결 되 며 이 항목 은 연결 되 어 있 습 니 다!
두 노드 사이 에 여러 개의 변 이 있 을 수 있 지만 한 변 의 양 끝 은 반드시 다른 노드 일 것 이다.
각 노드 마다 하나의 에너지 값 이 있다.
지금 우 리 는 프로젝트 관리 소프트웨어 를 만 들 려 고 합 니 다. 이 소프트웨어 는 두 가지 조작 이 있 습 니 다.
1. 어떤 항목 의 에너지 값 에 특정한 값 을 더 합 니 다.
2. 한 항목 과 인접 한 항목 의 에너지 값 의 합 을 묻는다.(여러 개의 변 이 있 으 면 여러 번, 예 를 들 어 a 와 b 가 두 개의 변 이 있 으 면 a 를 물 을 때 b 의 가중치 가 두 번 계산 된다).

Input
첫 번 째 줄 의 정수 T (1 < = T < = 3) 는 테스트 데이터 의 개 수 를 나타 낸다.
그리고 각 테스트 데이터 에 대해 첫 번 째 줄 은 두 개의 정수 n (1 < = n < = 100000) 과 m (1 < = m < = n + 10) 가 있 는데 각각 점수 와 변 수 를 나타 낸다.
그리고 m 줄, 줄 마다 두 개의 a 와 b 는 a 와 b 사이 에 한 변 이 있 음 을 나타 낸다.
그리고 정수 Q.
그리고 Q 줄, 줄 마다 첫 번 째 cmd 는 조작 유형 을 표시 합 니 다.cmd 가 0 이면 다음 두 개의 u v 는 프로젝트 u 의 에너지 값 에 v (0 < = v < = 100) 를 더 하 는 것 을 나타 낸다.
cmd 가 1 이면 다음 수 u 는 u 와 인접 한 프로젝트 의 에너지 값 의 합 을 물 어 보 는 것 을 나타 낸다.
모든 점 은 1 부터 n 까지 레이 블 입 니 다.

Output
모든 질문 에 한 줄 을 출력 하여 답 을 표시 합 니 다.

Sample Input

 
   
     1 3 2 1 2 1 3 6 0 1 15 0 3 4 1 1 1 3 0 2 33 1 2

Sample Output

 
   
     4 15 15

思路：

如果直接暴力，原则上是要TLE的，可惜这题数据比较水~

下面说说我的解法

每个点维护两个值，w[i]-该点的值、sum[i]-相邻节点值的和。

怎样在复杂度较小的范围内维护这两个值呢。

如果把与x相连的点分为两类，一类的度数大于它（该类不超过(2m)^(1/2)），另一类度数小于它。更新和查询时时只操作度数大于它的点，就能降低复杂度了。

一个点更新时度数大于它的相邻点是直接更新了的，查询大点时答案已经统计了，但是查询小点的时候答案这没有统计完，对于小点，这个点又为小点的大点，于是再遍历一下，将未更新的点更新维护sum数组即可。

复杂度就为 q*sqrt（m）了。

还有注意要将重边合并。

代码：

#include 
#include 
#include 
#include 
#include 
#define maxn 100005
#define MAXN 300005
using namespace std;

int n,m,ans,cnt,tot;
int head[maxn],dug[maxn];
int sum[maxn],w[maxn];
struct node
{
    int u,v,num;
} edge[MAXN];
struct Node
{
    int v,next,num,last;
} g[MAXN];

void addedge(int u,int v,int num)
{
    cnt++;
    g[cnt].v=v;
    g[cnt].num=num;
    g[cnt].next=head[u];
    head[u]=cnt;
}
bool cmp(node xx,node yy)
{
    if(xx.u!=yy.u) return xx.uv) swap(u,v);
            edge[i].u=u;
            edge[i].v=v;
            edge[i].num=1;
        }
        sort(edge+1,edge+m+1,cmp);
        tot=1;
        for(i=2; i<=m; i++)  //      
        {
            if(edge[i].u==edge[tot].u&&edge[i].v==edge[tot].v) edge[tot].num++;
            else edge[++tot]=edge[i];
        }
        for(i=1; i<=tot; i++) //     
        {
            dug[edge[i].u]++; dug[edge[i].v]++;
        }
        cnt=0;
        for(i=1; i<=tot; i++) //               
        {
            u=edge[i].u;
            v=edge[i].v;
            if(dug[v]>dug[u]) addedge(u,v,edge[i].num);
            else addedge(v,u,edge[i].num);
        }
        int q,op,val;
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d",&op);
            if(op==0)
            {
                scanf("%d%d",&u,&val);
                w[u]+=val;
                for(i=head[u]; i; i=g[i].next)  //      sum 
                {
                    v=g[i].v;
                    sum[v]+=g[i].num*val;
                }
            }
            else
            {
                scanf("%d",&u);
                ans=sum[u];
                for(i=head[u]; i; i=g[i].next) //           
                {
                    v=g[i].v;
                    if(g[i].last!=w[v])
                    {
                        ans+=g[i].num*(w[v]-g[i].last);
                        g[i].last=w[v];
                    }
                }
                sum[u]=ans;
                printf("%d
",ans);
            }
        }
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU 1874: 원활 한 공사 계속 [Dijkstra & SPFA & Floyd]

모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실행 한 후에 마침내 많은 길 을 건설 하 였 다.길 을 많이 건 너 지 않 아 도 좋 지 않다. 한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hdu 4858 프로젝트 관리 (그림 의 분할)

좋은 웹페이지 즐겨찾기