挖地雷（Mine）
在一个地图上有N 个地窖（N<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且从编号小的地窖通向编号大的地窖。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。
【输入格式】
N {地窖的个数}
W1，W2，……WN {每个地窖中的地雷数}
X1，Y1 {表示从X1可到Y1，保证xi小于yi}
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
【解题思路】
根据题目中规定路径都是单向的,且从编号小的地窖通向编号大的地窖，可以确定本题可以使用动态规划解决。首先思考求解时最后一步会做什么——选择最后一个地窖，挖走其中的地雷。
依据此来推出状态转移方程
设f[i]表示以i地窖为结束点能挖到的最大地雷数。
那么可以写出f[i]=max(f[j]+a[i])
条件是j小于i且j到i有通道连接。
挖地雷的路线可以在每次求f[i]时记住f[i]的值从哪里来，记住j值。
最后根据终点走回去即可。
不过我的程序使用了另一种方式，用动态数组记录现在走的路线。
【参考程序】
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,w[250],f[250],map[300][300],ans,x,y,choice;
vector<int> road[250];
int main()
{
freopen("mine.in","r",stdin);
freopen("mine.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>w[i];
f[i]=w[i];
road[i].push_back(i);
//输入，初始化，假设每一个地窖都以自己为起点和终点。
}
cin>>x>>y;
while (x!=0&&y!=0)
{
map[x][y]=true;//记录连线
cin>>x>>y;
}
for (int i=2;i<=n;i++)
{
choice=-1;
for (int j=1;j<i;j++)
if (map[j][i]&&f[i]<f[j]+w[i]) //判断条件
{
f[i]=f[j]+w[i];
choice=j;//记录选择
}
if (choice!=-1)
{
road[i].clear();//清除记录
for (int j=0;j<road[choice].size();j++)
road[i].push_back(road[choice][j]);//重新记录
road[i].push_back(i);//把终点压入
}
}
for (int i=1;i<=n;i++)
if (ans<f[i])
{
ans=f[i];
choice=i;
}
//求最大答案
cout<<road[choice][0];
for (int i=1;i<road[choice].size();i++) cout<<"-"<<road[choice][i];
cout<<endl<<ans;
return 0;
}