Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

求救啊!!!!!无限RE啊!我的方法好清晰,用线段树来动态维护欧拉序列,我测试了好久感觉没错,可总是RE,求大牛指点!!

Posted by beyondxgb at 2011-06-01 22:03:23 on Problem 2763
#include <iostream>
#include <vector>
using namespace std;

const int maxn=4*100005;

struct node
{
    int id,w,num;  //id表示编号,w为权值,num表示第几条路
};

struct tree   //线段树
{
  int l,r;
  int add;  //改变值
  int min;  //保存最小值
};

vector <node> v[maxn];
int st[maxn],en[maxn];  //dfs时每个结点第一次访问时的序号,最后一次访问时的序号
int e[maxn],ww[maxn];  // e[]为每条边的末端点,ww[] 表示第i条边的权值
int d[maxn],f[maxn],num[maxn]; //d[]为每一结点到根的距离,f[]为第一次访问结点时的序号,num[]保存欧拉序列每一点到根的距离
bool visit[maxn];
tree g[maxn];
int n,q,s,tt;  //s为始点,会改变,   tt为欧拉序列的结点数


int min(int a,int b)
{
    if (a<b) return a;
    else return b;
}

int max(int a,int b)
{
	if (a>b) return a;
	else return b;
}

void dfs(int u)
{
    tt++; f[u]=tt; num[tt]=d[u]; st[u]=tt;
    visit[u]=true;
    for (int i=0;i<(int)v[u].size();i++)
    {
        if (visit[v[u][i].id]==false)
        {
            d[v[u][i].id]=d[u]+v[u][i].w;
            e[v[u][i].num]=v[u][i].id;
			ww[v[u][i].num]=v[u][i].w;
            dfs(v[u][i].id);
            tt++; num[tt]=d[u];
        }
    }
    en[u]=tt;
}

void build(int l,int r,int t)
{
    g[t].l=l; g[t].r=r; g[t].add=0; g[t].min=999999999;
    if (l==r)
    {
        g[t].min=num[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,2*t);
    build(mid+1,r,2*t+1);
    g[t].min=min(g[2*t].min,g[2*t+1].min);
}

int find(int l,int r,int t)
{
    if (g[t].l==l && g[t].r==r)
    {
        return g[t].min;
    }

    g[2*t].add+=g[t].add; g[2*t+1].add+=g[t].add;
    g[2*t].min+=g[t].add; g[2*t+1].min+=g[t].add;
    g[t].add=0;

    int mid=(g[t].l+g[t].r)/2;
    if (l>=mid+1)
        return find(l,r,2*t+1);
    else if (r<=mid)
        return find(l,r,2*t);
    else
    {
        return min(find(l,mid,2*t),find(mid+1,r,2*t+1));
    }
}

void insert(int l,int r,int t,int k)
{
    if (g[t].l==l && g[t].r==r)
    {
        g[t].add+=k;
        g[t].min+=k;
        return ;
    }

    g[2*t].add+=g[t].add; g[2*t+1].add+=g[t].add;
    g[2*t].min+=g[t].add; g[2*t+1].min+=g[t].add;
    g[t].add=0;

    int mid=(g[t].l+g[t].r)/2;
    if (l>=mid+1)
        insert(l,r,2*t+1,k);
    else if (r<=mid)
        insert(l,r,2*t,k);
    else
    {
        insert(l,mid,2*t,k);
        insert(mid+1,r,2*t+1,k);
    }
    g[t].min=min(g[2*t].min,g[2*t+1].min);

}

void init()
{
    for (int i=1;i<=n;i++)
    {
        v[i].clear();
    }
}

int main()
{
    int i,a,b,c,ee;
    while (scanf("%d%d%d",&n,&q,&s))
    {
        init();
        for (i=1;i<=n-1;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            node p;
            p.id=b; p.w=c; p.num=i;
            v[a].push_back(p);
            p.id=a; p.w=c; p.num=i;
            v[b].push_back(p);
        }
        memset(visit,false,sizeof(visit));
        tt=0; d[1]=0;
        dfs(1);
 /*       for (i=1;i<=n;i++) printf("%d ",d[i]);
        printf("\n");
        for (i=1;i<=2*n-1;i++) printf("%d ",num[i]);
        printf("\n");
        for (i=1;i<=n;i++) printf("%d ",f[i]);
        printf("\n");
        for (i=1;i<=n;i++) printf("%d ",en[i]);
        printf("\n");
*/
        build(1,tt,1);
        while(q--)
        {
            scanf("%d",&a);
            if (a==0)
            {
                scanf("%d",&ee);
                int ans=find(min(f[s],f[ee]),max(f[s],f[ee]),1); //返回公共祖先到根的距离
                printf("%d\n",find(f[s],f[s],1)+find(f[ee],f[ee],1)-2*ans);
                s=ee;
            }
            else
            {
                scanf("%d%d",&b,&c);
                //当一条边的权值改变时,改变欧拉序列的一段,对应以其为根的下边的点都改变了,区间为这一个点在欧拉序列第一次出现的位置到最后一次出现的位置
                insert(st[e[b]],en[e[b]],1,c-ww[b]); 
            }
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator