挖地雷

　在一个地图上有N个地窖（N<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

【输入格式】

　　N  {地窖的个数}

　　W1，W2，……WN　　 {每个地窖中的地雷数}

　　X1，Y1　　　　　　 {表示从X1可到Y1}

　　X2，Y2

　　 ……

　　0 ，0　　　　　　  {表示输入结束}

【输出格式】

　　K1—K2—……—Kv   {挖地雷的顺序}

　　MAX　　　　　　　　{最多挖出的地雷数}

【输入样例】Mine.in

　　6

　　5 10 20 5 4 5

　　1 2

　　1 4

　　2 4

　　3 4

　　4 5

　　4 6

　　5 6

　　0 0

【输出样例】Mine.out

　　3-4-5-6

　　34

题意

题解#include <cstdio>

#include <iostream>

#include <algorithm>

int i,j,k,l,m,n;

int a[300][300],b[300],c[300],d[300];

int main()

{

scanf("%d",&n);

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

scanf("%d",&b[i]);

scanf("%d%d",&k,&l);

a[k][l]=1;

while (k!=0&&l!=0)

{

scanf("%d%d",&k,&l);

a[k][l]=1;

}

c[n]=b[n]; //初始化最后一个地窖 

for (i=n-1;i>=1;i--)//循环寻找最优解 ，因为动规的无后效性从最后开始 

{

l=0;k=0;

for (j=i+1;j<=n;j++)//查看是否联通，找出最大的地雷数 

if (a[i][j]==1&&c[j]>l)

{

l=c[j];

k=j;

}

c[i]=l+b[i];//更新当前的最优值 

d[i]=k;

}

k=1;

for (j=2;j<=n;j++)//寻找最大值 

if (c[j]>c[k]) k=j;

m=c[k];

printf("%d",k);

k=d[k];

while (k!=0)//输出路径 

{

printf("-%d",k);

k=d[k];

}

printf("\n");

printf("%d",m);

}