华师一附中OI组

标题: P2196 挖地雷 [打印本页]
作者: universehyf    时间: 2018-10-15 21:40
标题: P2196 挖地雷
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    时间: 2018-10-15 21:40
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2