http://acm.timus.ru/problem.aspx?space=1&num=1078主要思路:i包含j连一有向边i->j,这样问题就变成了给一个有向无环图(DAG),求其最长路,直接spfa就OK啦!
Code
#include<cstdio>
#define MAXN 501
int graph[MAXN][MAXN];
int rd[MAXN];
int dist[MAXN];
int pre[MAXN];
int mark[MAXN];
int seg[MAXN][2];
int maxLen;
int n;
int isContains(int I, int J){
int reVal = 0;
if(seg[I][0] < seg[J][0] && seg[I][1] > seg[J][1]){
reVal = 1;
}
if(seg[J][0] < seg[I][0] && seg[J][1] > seg[I][1]){
reVal = -1;
}
return reVal;
}
void spfa(){
int i = 0;
int I = 0;
int t = 0;
int qHead = 0;
int qTail = 0;
int Q[MAXN] = {0};
for(i = 0; i < n; i++){
mark[i] = 0;
pre[i] = -1;
dist[i] = -MAXN;
}
for(i = 0; i < n; i++){
if(!rd[i]){
Q[qHead++] = i;
mark[i] = 1;
dist[i] = 1;
}
}
do{
qHead--;
if(qHead < 0){
qHead = n - 1;
}
I = Q[qHead];
mark[I] = 0;
for(i = 0; i < n; i++){
if(graph[I][i] && dist[I] + 1 > dist[i]){
pre[i] = I;
dist[i] = dist[I] + 1;
if(!mark[i]){
mark[i] = 1;
t = qHead - 1;
if(t < 0)t = n - 1;
if(qHead != qTail
&& dist[i] < dist[Q[t]]){
Q[qHead++] = i;
if(qHead >= n){
qHead = 0;
}
}
else{
qTail--;
if(qTail < 0){
qTail = n - 1;
}
Q[qTail] = i;
}
}
}
}
}while(qHead != qTail);
maxLen = -1;
for(i = 0, I = -1; i < n; i++){
if(dist[i] > maxLen){
maxLen = dist[i];
I = i;
}
}
printf("%d\n", maxLen);
t = I;
i = 0;
while(t != -1){
if(i){
printf(" ");
}
i = 1;
printf("%d", t + 1);
t = pre[t];
}
printf("\n");
}
int main(int argc, char* argv[], char* env[])
{
int i = 0;
int j = 0;
int t = 0;
while(scanf("%d", &n) != EOF){
for(i = 0; i < n; i++){
scanf("%d%d", &seg[i][0], &seg[i][1]);
}
for(i = 0; i < n; i++){
rd[i] = 0;
graph[i][i] = 0;
for(j = i + 1; j < n; j++){
t = isContains(i, j);
graph[i][j] = t > 0 ? 1 : 0;
graph[j][i] = t < 0 ? 1 : 0;
}
}
for(j = 0; j < n; j++){
for(i = 0; i < n; i++){
rd[j] += graph[i][j];
}
}
spfa();
}
return 0;
}
posted on 2011-07-20 10:59
Lshain 阅读(301)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm 、
题解-timus