洛谷 P2196 [NOIP 1996 提高组] 挖地雷

张开发
• 2026/4/5 1:26:47 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

洛谷 P2196 [NOIP 1996 提高组] 挖地雷
题目描述在一个地图上有 N (N≤20) 个地窖每个地窖中埋有一定数量的地雷。同时给出地窖之间的连接路径。当地窖及其连接的数据给出之后某人可以从任一处开始挖地雷然后每次可以移动到一个编号比当前节点大且联通的节点去挖地雷当无满足条件的节点时挖地雷工作结束。设计一个挖地雷的方案使某人能挖到最多的地雷。输入格式有若干行。第 1 行只有一个数字表示地窖的个数 N。第 2 行有 N 个数分别表示每个地窖中的地雷个数。第 3 行至第 N1 行表示地窖之间的连接情况第 3 行有 n−1 个数0 或 1表示第一个地窖至第 2 个、第 3 个 … 第 n 个地窖有否路径连接。如第 3 行为 1 1 0 0 0⋯0则表示第 1 个地窖至第 2 个地窖有路径至第 3 个地窖有路径至第 4 个地窖、第 5 个 … 第 n 个地窖没有路径。第 4 行有 n−2 个数表示第二个地窖至第 3 个、第 4 个 … 第 n 个地窖有否路径连接。……第 n1 行有 1 个数表示第 n−1 个地窖至第 n 个地窖有否路径连接。为 0 表示没有路径为 1 表示有路径。输出格式第一行表示挖得最多地雷时的挖地雷的顺序各地窖序号间以一个空格分隔不得有多余的空格。第二行只有一个数表示能挖到的最多地雷数。输入输出样例输入 #1复制5 10 8 4 7 6 1 1 1 0 0 0 0 1 1 1输出 #1复制1 3 4 5 27说明/提示【样例解释】最优路径为 1→3→4→5结果为 27。【题目来源】NOIP 1996 提高组第三题。#includebits/stdc.h using namespace std; const int N25; int e[N][N],cnt[N],pre[N],f[N]; void dfs(int x) { if(pre[x]) dfs(pre[x]); coutx ; } int main() { int n; cinn; for(int i1;in;i) { cincnt[i]; } for(int i1;in;i) { for(int ji1;jn;j) { cine[i][j]; } } for(int i1;in;i) { f[i]cnt[i]; for(int j1;ji;j) { if(e[j][i]) { if(f[j]cnt[i]f[i]) { f[i]f[j]cnt[i]; pre[i]j; } } } } int pos0,ans0; for(int i1;in;i) { if(f[i]ans) { ansf[i]; posi; } } dfs(pos); coutendlansendl; return 0; }

更多文章