#include<bits/stdc++.h> 

using namespace std; 

long f[201]={0},w[201],c[201]={0}; 

bool a[201][201]={0}; 

long i,j,n,x,y,l,k,maxx; 

int main() 

{ 

 memset(f,0,sizeof(f));//f 数组记录从第 i 个地窖开始最多可以挖出的地雷数 

 memset(c,0,sizeof(c));//c 数组记录后继结点 

 memset(a,false,sizeof(a));//a 数组记录是否有通路 

 scanf("%d",&n); 

 for (i=1;i<=n;i++) 

 { 

 scanf("%d",&w[i]);//输入每个地窖中的地雷数 

 }  

 do 

 {  

 scanf("%d%d",&x,&y);//表示从 X 可到 Y 

 if ((x!=0)&&(y!=0)) a[x][y]=true;//表示可以从 x 到 y  

 }while ((x!=0)||(y!=0)); 

 f[n]=w[n];//从后 F[n]往前逐个找出所有的 F[i] 

 for (i=n-1;i>=1;i--) 

 { 

 l=0;//最大地雷数 

 k=0;//后继结点 

 //遍历后继结点 

 for (j=i+1;j<=n;j++) 

 { 

 if ((a[i][j])&&(f[j]>l)) 

 {  

 l=f[j];//更新最大地雷数 

 k=j;//更新后继结点 

} 

 } 

 f[i]=l+w[i];//保存从第 i 个地窖起能挖到最大地雷数 

 c[i]=k;//k 地窖是 i 地窖最优路径 

 } 

 k=1; 

 for (j=2;j<=n;j++)//计算最多挖出的地雷数 

 { 

 if(f[j]>f[k]) k=j;//寻找位置 

}  maxx=f[k];//找到最大地雷数 

 printf("%d",k);//打印起始点 

 k=c[k];//后继结点 

 while (k!=0)//输出挖地雷的顺序 

 { 

 printf("-%d",k); 

 k=c[k]; 

 }  

 printf("\\n%d",maxx);//输出最多挖出的地雷数 

 return 0;  

}

这也是一篇很详细的题解哦

也可反向记录

#include<bits/stdc++.h>
using namespace std;
int yuan[201],f[201],qian[201],n,x,y,k=0,shu;
bool lu[201][201];
void pr(int n){
	if(!n)return;
	pr(qian[n]);
	cout<<n<<"-";
	return; 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){cin>>yuan[i];f[i]=yuan[i];}
	do{cin>>x>>y; 
	lu[y][x]=true;   
    }while(x&&y);
    for(int i=2;i<=n;i++)
       for(int o=1;o<i;o++)
          if(lu[i][o]==1&&yuan[i]+f[o]>f[i]){f[i]=yuan[i]+f[o];qian[i]=o;}
    for(int i=1;i<=n;i++)
	  if(k<f[i]){k=f[i];shu=i;}
    pr(qian[shu]);
    cout<<shu<<endl<<f[shu];
	return 0;
}

#include
using namespace std;
long long f[201],w[201],c[201];//w数组是每个地窖中地雷的数量，c数组是路径，f是到达第x地窖最大地雷数
bool a[201][201];//存储从x到y有路径
long long i,j,n,x,y,l,k,max1;//l是从前一个地窖到这个地窖所能挖到的最大地雷数
int main()//k是暂时存储最优路径
{
cin>>n;
for(i=1;i<=n;i++)
cin>>w[i];//华丽的输入~
do
{
cin>>x>>y;//表从x到y~
if((x!=0)&&(y!=0)) a[x][y]=true;//表示从x地窖到y地窖有路
}while((x!=0)||(y!=0));//读入到零终止
f[n]=w[n];//动态规划的边界（倒退所以是从第n个开始的）
for(i=n-1;i>=1;i--)//逆推
{
l=0;k=0;//初始化
for(j=i+1;j<=n;j++)//枚举第i到第i-1的地窖
{
if((a[i][j])&&(f[j]>l))//如果有路并且地窖中的地雷大于现有的
{
l=f[j];//保存最大数目
k=j;//保存路径
}
f[i]=l+w[i];
c[i]=k;
}
}
k=1;//从第一个开始
for(j=2;j<=n;j++)
{
if(f[j]>f[k]) k=j;//打擂台找最大
}
max1=f[k];//保存最大值
cout<<k;//开始输出路径
k=c[k];
while(k!=0)
{
cout<<"-"<<k;
k=c[k];
}//逐个输出路径~
cout<<endl;
cout<<max1<<endl;
return 0;//华丽的结束~芜湖直接ac

} 写的真的很详细了，希望有帮助（毕竟我卡了很久很久） 关爱生命，禁止抄袭