您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

P2196 [NOIP1996 提高组] 挖地雷(dfs+记录路径)

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false);

int n;
int bom[25];
int path[25];
int tmp[25];
int Max;
int P;
int lnk[25][25];
void dfs(int pos, int x, int sum) {
	if (Max < sum) {
		for (int i = 1; i <= pos; i++) {
			path[i] = tmp[i];
		}
		P = pos;
		Max = sum;
	}
	for (int i = x + 1; i <= n; i++) {
		if (lnk[x][i]) {
			tmp[pos + 1] = i;
			dfs(pos + 1, i, sum + bom[i]);
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", bom + i);
	}
	for (int i = 1; i <= n - 1; i++) {
		for (int j = i + 1; j <= n; j++) {
			scanf("%d", &lnk[i][j]);
		}
	}
	for (int i = 1; i <= n; i++) {
		tmp[1] = i;
		dfs(1, i, bom[i]);
	}
	for (int i = 1; i <= P; i++) {
		printf("%d ", path[i]);
	}
	printf("\n%d", Max);
	return 0;
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进