【題目描述】

在一個地圖上有n個地窖（n≤200）,每個地窖中埋有一定數量的地雷。同時，給出地窖之間的連接路徑，并規定路徑都是單向的,且保證都是小序號地窖指向在序號地窖，也不存在可以從一個地窖出發經過若干地窖后又回到原來地窖的路徑。某人可以從任一處開始挖地雷，然后沿著指出的連接往下挖（僅能選擇一條路徑），當無連接時挖地雷工作結束。設計一個挖地雷的方案，使他能挖到最多的地雷。

【輸入】

第一行：地窖的個數；

第二行為依次每個地窖地雷的個數；

下面若干行：

xi yi ?//表示從xi可到yi，xi<yi。

最后一行為"0 0"表示結束。

【輸出】

k1?k2?…?kv ? //挖地雷的順序
挖到最多的雷。

【輸入樣例】

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

【輸出樣例】

3-4-5-6
34

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 201 #define MOD 2520 #define E 1e-12 using namespace std; int g[N][N]; int w[N],pre[N]; int f[N]; void print(int k) {if(k==0)return;print(pre[k]);if(pre[k]==0)cout<<k;elsecout<<"-"<<k; } int main() {int n;cin>>n;for(int i=1;i<=n;i++){cin>>w[i];f[i]=w[i];}int x,y;while(scanf("%d%d",&x,&y)!=EOF&&x&&y)g[x][y]=1;int maxx=-INF,k;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if( g[j][i]==1 && f[j]+w[i]>f[i] ){f[i]=f[j]+w[i];pre[i]=j;}}if(f[i]>maxx){maxx=f[i];k=i;}}print(k);cout<<endl<<maxx<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的挖地雷（信息学奥赛一本通-T1262）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。