挖地雷

Problem Description

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

Input

输入有多组数据，每组数据的第一行为一个整数n，表示地窖的个数，第二行为n个地窖中的地雷数。下面多行数据以0,0结束，每行为两个数x和y，表示从x可以到y。

Output

对于每组数据输出两行，第一行为挖地雷的顺序，第二行为最多挖出的地雷数

Sample Input

6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0

Sample Output

3-4-5-6
34
【代码】

#include<iostream>
#include<cstdio>
using namespace std;
const int maxx=1001;
int w[maxx],a[maxx][maxx],f[maxx],c[maxx];//w为每个地窖的地雷数目，a为地窖与地窖之间是否连通,f记录从每个地窖开始挖最多能挖多少，c为记录路径 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&w[i]);
    int x,y;
    do
    {
     scanf("%d%d",&x,&y);
     if(x!=0&&y!=0)
     a[x][y]=1;    
    }while(x!=0&&y!=0);
    f[n]=w[n];//最后一个地窖开始能挖的就只有他自己的了，因为没有和它连着的地窖 
    for(int i=n-1;i>=1;i--)//从后往前 
    {
        int l=0,k=0;
        for(int j=i+1;j<=n;j++)
        {
            if(a[i][j]&&f[j]>l)//这两个地窖相连并且要选一条能挖地雷最多的道路 
            {
                l=f[j];//找最大 
                k=j;//记录答案 
            }
        }
        f[i]=w[i]+l;//从i从发能挖的地雷 
        c[i]=k;//记录前驱 
    }
    int k=1;
    for(int i=1;i<=n;i++)
    {
        if(f[i]>f[k])//寻找能挖地雷最多的 
        k=i;
    }
    cout<<f[k]<<endl;//输出挖的地雷 
    cout<<k;//输出道路 
    k=c[k];
    while(k!=0)
    {
        cout<<"-"<<k;
        k=c[k];
    }
    cout<<endl;
    return 0;
}