2570 - 挖地雷
在一个地图上有N个地窖（N<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。
Input
第一行一个整数n表示有n个地窖
第二行有n个整数表示每个地窖的地雷数
以下有若干行，每行有两个数x,y表示x可以到y，保证x小于y。
最后一行有两个0，表示输入结束
Output
第一行输出挖地雷的顺序。
第二行为最多挖出的地雷数
Examples
Input
6 5 10 20 5 4 5 1 2 1 4 2 4 3 4 4 5 4 6 5 6 0 0
Output
3-4-5-6 34
Solution C
#include "stdio.h" int n; int max,s,e; int a[201],f[201][201]; void F() { int i; if(s==e) { printf("%d\n",e); return ; } printf("%d-",s,e); for(i=s+1;i<=e;i++) if(f[s][i]+f[i][e]-a[i]==f[s][e]) { s=i; F(); return; } } int main() { int i,j,k; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); f[i][i]=a[i]; } scanf("%d%d",&s,&e); while(s&&e) { f[s][e]=a[s]+a[e]; scanf("%d%d",&s,&e); } s=e=0; for(i=1;i<=n;i++) { for(j=i;j>0;j--) { for(k=j;k<=i;k++) { if(f[j][k]&&f[k][i]&&f[j][i]<f[j][k]+f[k][i]-a[k]) f[j][i]=f[j][k]+f[k][i]-a[k]; } if(f[j][i]>f[s][e]) s=j,e=i; } } max=f[s][e]; F(); printf("%d\n",max); return 0; }
Solution C++
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,a[201],b[201],f[201],g[201][201]={0};//f[i]数组表示从第i个地窖起挖 void init(); void work(); int main() { init(); work(); return 0; } void init() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; while(1) { int x,y; cin>>x>>y; if(x==0)break; g[x][y]=1; } } void work() { f[n]=a[n]; for(int i=n-1;i>0;i--) { int my_max=0,k=0; for(int j=i+1;j<=n;j++) { if(g[i][j]&&f[j]>my_max) { my_max=f[j]; k=j; } } f[i]=my_max+a[i]; //cout<<"i="<<i<<' '<<k<<' '<<f[i]<<endl; b[i]=k; } int tot=0,k=0; //for(int i=1;i<=n;i++)cout<<f[i]<<' '; for(int i=1;i<=n;i++)if(tot<f[i]){tot=f[i];k=i;} cout<<k; k=b[k]; while(k!=0) { cout<<'-'<<k; k=b[k]; } cout<<endl; cout<<tot<<endl; }