| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
大家帮忙看一下 为什么我用 RMQ算法会 RE???#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator