P2196 挖地雷

universehyf

https://www.luogu.org/problemnew/show/P2196题目背景

NOIp1996提高组第三题

题目描述

在一个地图上有NN个地窖(N \le 20)(N≤20)，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入输出格式输入格式：

有若干行。

第11行只有一个数字，表示地窖的个数NN。

第22行有NN个数，分别表示每个地窖中的地雷个数。

第33行至第N+1N+1行表示地窖之间的连接情况：

第33行有n-1n−1个数（00或11），表示第一个地窖至第22个、第33个、…、第nn个地窖有否路径连接。如第33行为1 1 0 0 0 … 011000…0，则表示第11个地窖至第22个地窖有路径，至第33个地窖有路径，至第44个地窖、第55个、…、第nn个地窖没有路径。

第44行有n-2n−2个数，表示第二个地窖至第33个、第44个、…、第nn个地窖有否路径连接。

… …

第n+1n+1行有11个数，表示第n-1n−1个地窖至第nn个地窖有否路径连接。（为00表示没有路径，为11表示有路径）。

输出格式：

有两行

第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

输入输出样例输入样例#1：

[size=1.2][url=]复制[/url]

510 8 4 7 61 1 1 00 0 01 11
输出样例#1：

[size=1.2][url=]复制[/url]

1 3 4 527

universehyf

1. #include<iostream>
   
2. using namespace std;
   
3. #define FOR(i,n,m) for(int i=n;i<=m;i++)
   
4. #define For(i,n,m) for(int i=n;i>=m;i--)
   
5. bool b[210][210];
   
6. int w[210],f[210],g[210],n,k,maxn;
   
7. int main()
   
8. {
   
9.     cin>>n;FOR(i,1,n) cin>>w[i];
   
10.     FOR(i,1,n-1) FOR(j,i+1,n) {cin>>k;if(k==0)b[i][j]=0;else b[i][j]=1;}
    
11.     f[n]=w[n];
    
12.     For(i,n,1) {
    
13.         f[i]=w[i];
    
14.         FOR(j,i+1,n)
    
15.             if(b[i][j]&&w[i]+f[j]>f[i]){
    
16.                 f[i]=w[i]+f[j];
    
17.                 g[i]=j;
    
18.         }
    
19.     }
    
20.     FOR(i,1,n) if(f[i]>maxn) {k=i;maxn=f[i];}
    
21.     cout<<k;while(g[k]!=0){k=g[k];cout<<" "<<k;}
    
22.     cout<<endl<<maxn;
    
23.     return 0;
    
24. }

复制代码