编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

感谢题解帮我读懂了题！我开始看样例还以为是求最长路径的长度和路径上的点，后来才知道是求最长路径和所有最长路径上的点！

我先SPFA求了1到n+1的最长路长度，然后再DFS，条件是点在一条最长路上

procedure dfs(x:longint);

……

if long[i]+road=long[x] then dfs(i);

……

然后输出所有的被DFS到的点就行了

搞了半天才理解题目什么意思，实际很简单，就是求从1到n+1的最长路径长度以及哪些点在最长路径上（注意：如果有多条最长路径，每条路径的点都算）。方法也很简单，无限制做DFS就行了（但是要防止环）。建议使用集合，这样写起来比较方便。

看完题解A了。。。完全不知道各位大牛从哪里看出这题问什么。。。。。。。。。。。。。。。我看了N次完全不知道他要求什么。现在知道求什么后也不知道。你们从哪里看出来的。。郁闷啊

真可惜！只对了六个测试点

高手们帮帮我吧！！！！！！

#include "stdio.h"

#include "stdlib.h"

#define M 100

struct node

{

int v;

int w;

struct node *next;

};

struct

{

int din;

int sum;

struct node *next;

}s[M];

int a[M],la=0,b[M],lb=0,min;

void CreatG(int n,int e)

{

int vi,vj,w;

struct node *p;

for(int i=1;iw=w;

p->next=s[vi].next;

s[vi].next=p;

s[vj].din++;

}

}

void AVO(int n)

{

int q[M],top=0,x;

struct node *p;

for(int i=1;iv].sumw+s[x].sum)

s[p->v].sum=p->w+s[x].sum;

s[p->v].din--;

if(s[p->v].din==0)

{

q[top++]=p->v;

a[la++]=p->v;

}

p=p->next;

}

}

if(la==n)

{

b[lb++]=a[--la];

min=s[n].sum;

printf("%d\n",min);

while(la)

{

p=s[a[--la]].next;

while(p)

{

if(p->v==b[lb-1])

{

if(s[a[la]].sum==min-p->w)

{

b[lb++]=a[la];

min-=p->w;

}

break;

}

p=p->next;

}

}

int t;

for(int i=0;i

我也是第8组不过...

开始爆栈..现在...

├ 测试数据 08：答案错误...程序输出比正确答案长...

虽然我以为只要多加一条判断就可以解决这个问题#24

怎么对付第八组的环？

Accepted 有效得分：100 有效耗时：0ms

今天做的第N个Floyd了。。

想当年以为是关键路径囧，，

该题求最长路的值dfs就可以了

注意dfs的时候该路径不能存在环

求经过点的话可以DFS两次

设r1[i]为1到i的最长路,r2[i]为i到n+1的最长路

显然最长路len=r1[n+1]=r2[1]

那么i是路径上的点 当且仅当 r1[i]+r2[i]等于len

对于1,5错的

注意是所有可能的路径。

也就是说长度一样的路径都被包含在内了。

用邻接表存图

无限制DFS 保留最大路径

var

n,m,i,j,x,y,z:longint;

vis:array[1..101]of boolean;

q:array[1..10000]of longint;

sum,sum1:array[1..101]of longint;

a,b:array[1..101,1..100]of record x,y:longint;end;

dis,dis1:array[1..101]of longint;

procedure spfa1;

var l,r,j:longint;

begin

fillchar(vis,sizeof(vis),false);

for i:=2 to n+1 do

dis1[i]:=-maxlongint;

dis1[n+1]:=-dis[n+1];

l:=0;r:=1;

vis[n+1]:=true;

q[1]:=n+1;

repeat

inc(l);

j:=q[l];

for i:=1 to sum1[j] do

if dis1[b[j,i].x]r;

end;

procedure spfa;

var l,r,j:longint;

begin

fillchar(vis,sizeof(vis),false);

for i:=2 to n+1 do

dis[i]:=-maxlongint;

dis[1]:=0;

l:=0;r:=1;

vis[1]:=true;

q[1]:=1;

repeat

inc(l);

j:=q[l];

for i:=1 to sum[j] do

if dis[a[j,i].x]r;

end;

begin

read(n);

read(m);

fillchar(sum,sizeof(sum),0);

fillchar(sum1,sizeof(sum1),0);

for i:=1 to m do

begin

readln(x,y,z);

inc(sum[x]);

a[x,sum[x]].x:=y;

a[x,sum[x]].y:=z;

inc(sum1[y]);

b[y,sum1[y]].x:=x;

b[y,sum1[y]].y:=z;

end;

spfa;

writeln(dis[n+1]);

spfa1;

for i:=1 to n+1 do

if dis[i]+dis1[i]=0

then write(i,' ');

END.

为什么只过三个点,请大牛指示!!谢谢!!或测试数据!!

对于那些1 5 有误的OIER，提供可能的两个原因：

1：题目要求是输出所有可能的点，可能最大的路径不止一条，所以每条上的都要输出

2：最后输出路径的时候如果是DFS注意变量要打在里面

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

Fuck them all

乱搞

spfa bfs 找路径 排序

直接DFS秒杀

不是经典AOE！！

第八点有环

大家直接些一个DFS直接过，试试吧，不用cheat的

数据是没有错的

其实数据出的很好的。。。

译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

郁闷....三次AC，前两次都是把集合中的尾数写错了...

递归才是王道！

MS 是典型的AOE网算法啊！！！！

两次spfa,if dis[i]+dis2[i]=0 then write(i ,' ');就这个

一次ac ._.

大牛能说下第1第5个点的路径输出有什么要求的吗？。。。被弄得郁闷死。。。前面对。。后面一直错- -

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：70 有效耗时：0ms

啊啊！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案错误...程序输出比正确答案长

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

怎么对付环？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

感谢EMANON！！