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