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

大家帮忙看一下 为什么我用 RMQ算法会 RE???

Posted by abilitytao at 2009-09-22 00:34:46 on Problem 1330
#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
vector<int>hash[10001];//用vector代替邻接表

#define MAXN   10001
#define mmin(seq, a, b)  ((seq[a] < seq[b]) ? (a) : (b))
int indegree[MAXN];
/**///// DP status
int fij[MAXN][100];

template <typename T>
void st(T seq[], int n)//预处理
{ 
    memset(fij, 0, 100 * MAXN * sizeof(int));
    int k = (int)(log((double)n) / log(2.0)); 
    /**/////初始状态
    for(int i = 0; i < n; i++)
        fij[i][0] = i; 
    /**/////递推计算状态
    for(int j = 1; j <= k; j++)
    {
        for(int i = 0; i + (1 << j) - 1 < n; i++)
        {
            //
            int m = i + (1 << (j - 1)); 
            //fij[i][j] = seq[fij[i][j - 1]] < seq[fij[m][j - 1]] ? fij[i][j - 1] : fij[m][j - 1];
            fij[i][j] = mmin(seq, fij[i][j - 1], fij[m][j - 1]);
        }
    }
}
template <typename T>
int RMQ(T seq[], int i, int j)//求解RMQ
{
    /**///// 用对2去对数的方法求出k
    int k = (int)(log(double(j - i + 1)) / log(2.0)); 
    /**/////
    //int t = seq[fij[i][k]] < seq[fij[j - (1 << k) + 1][k]] ? fij[i][k] : fij[j - (1 << k) + 1][k];
    int t = mmin(seq, fij[i][k], fij[j - (1 << k) + 1][k]);
    return t;
}

short E[MAXN*10];
int R[MAXN];
short D[MAXN*10];
int p=0;
void dfs(int r,int deep)//深搜,算出E,R,D数组
{
	p++;
	E[p]=r;
	D[p]=deep;
	R[r]=p;
	int i;
	int size=hash[r].size();
	for(i=0;i<size;i++)
	{

		dfs(hash[r][i],deep+1);
		p++;
		E[p]=r;
		D[p]=deep;
	}
	
}

int main()
{

	int testcase;
	int n;
	int i,j;
	int s,t;
	scanf("%d",&testcase);
	for(i=1;i<=testcase;i++)
	{
	
		scanf("%d",&n);
		for(j=1;j<=n;j++)
		{
			indegree[j]=0;
			hash[j].clear();
		}
		p=0;
			
		for(j=1;j<n;j++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			hash[a].push_back(b);
			indegree[b]++;
		}
		scanf("%d%d",&s,&t);
		int root;
		for(j=1;j<=n;j++)
		{

			if(indegree[j]==0)
			{
				root=j;
				break;
			}
		}
		dfs(root,0);
		st(D,2*n);
		if(R[s]<R[t])
			printf("%d\n",E[  RMQ(D,R[s],R[t]) ] );
		else
			printf("%d\n",E[ RMQ(D,R[t],R[s]) ] );

	}
	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