YCOJ挖地雷

挖地雷

Description

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

第一行一个整数n表示有n个地窖
第二行有n个整数表示每个地窖的地雷数
以下有若干行，每行有两个数x,y表示x可以到y，保证x小于y。
最后一行有两个0，表示输入结束

Output

第一行输出挖地雷的顺序。

第二行为最多挖出的地雷数

Sample Input 1

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 1

3-4-5-6
34
——摘自YCOJ

从题目得知，这是一个有向图。

也就是说，1可以到2，但2一定不能到1。

嗯~可爱的代码：

#include<bits/stdc++.h>
using namespace std;
int b[1000][1000];
int fa[1000],mp[1000],a[1000];
int n,x,y,ans;
int mx,maxn;
int main(){
 cin>>n;
for(int i=1;i<=n;i++){
        cin>>mp[i];
        
}
do{
    cin>>x>>y;
   if(x!=0&&y!=0){
   b[x][y]=1; 
}
 }while(x!=0||y!=0);
 fa[n]=mp[n];
        for(int i=n-1;i>=1;i--){
        	mx=maxn=0;
            for(int j=i+1;j<=n;j++)
                if(b[i][j]&&fa[j]>mx)mx=fa[j],maxn=j;
                    fa[i]=mx+mp[i];
					a[i]=maxn;
        }
            mx=maxn=0;
for(int i=1;i<=n;i++)
    if(fa[i]>maxn){
        maxn=fa[i],mx=i;
}
 ans=maxn;
 cout<<mx;
 while(a[mx]){
        cout<<"-"<<a[mx];
        mx=a[mx];
 }
 cout<<endl;
 cout<<ans<<endl;
 return 0;
}