Gridea

题目链接：https://www.luogu.com.cn/problem/P6248

这道题目是一个搜索题，数据范围很小，但是不可以直接暴搜，否则直接 TLE，但是由于题目说选择 $6$ 个人，所以可以略加剪枝，时间复杂度从 $2^n\times m$ 转为 $C_n^6\times m$ 了，可以通过本题。输入的名字可以用 map 存起来，而且可以利用位运算省去回溯。

#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 30 + 10;
FILE *fin, *fout;
inline int read(int &x) {
	char c = 0; int f = x = 0;
	while (c < 48 || c > 57) {
		if (c == -1) return 0;
		if (c == '-') f = 1; c = fgetc(fin);
	}
	while (c > 47 && c < 58) x = (x << 3) + (x << 1) + (c & 15), c = fgetc(fin);
	if (f) x = -x; return 1;
}
inline int read(string &s) {
	s = ""; char c = 0;
	while (c == 32 || c == 10 || c == 13 || c == 0) c = fgetc(fin); if (c == -1) return 0;
	while (!(c == 32 || c == 10 || c == 13 || c == 0 || c == -1)) s += c, c = fgetc(fin);
	return 1;
}
template<class T, class... Args> inline int read(T &x, Args&... args) {
	return read(x) + read(args...);
}
inline int write(int x) {
	if (x < 0) return fputc(45, fout), write(-x);
	if (x > 9) write(x / 10);
	return fputc((x % 10) | 48, fout), 1;
}
string name, u, v;
map<string, int> ma;//ma[s]表示名字为s的人的下标
int n, m, ans, a[N], k[N], gay[N];//a[i]表示第i个人的初始实力，k[i]表示第i对人新增的实力，gay[i]表示第i对人的两个下标，从0开始，例如10(1010)表示1号和3号可以新增实力
void dfs(int x, int y, int res, int bit) {//x表示现在到了第x个人，y表示选择了y个人，res表示目前的总实力，bit表示选择的人，例如22(10110)表示选择了1、2、4号
	if (n - x + y < 6) return;//要是到结尾都不能选够6个人，直接返回
	if (y == 6) {//如果选择了6个人了
		for (int i = 0; i < m; ++i)//每个gay都枚举一遍
			if ((bit & gay[i]) == gay[i])
				res += k[i];
		ans = max(ans, res);
		return;
	}
	if (x == n) return;
	dfs(x + 1, y, res, bit);//不选
	dfs(x + 1, y + 1, res + a[x], bit | (1 << x));//选，或上第x个人
}
int main() {
	#ifdef ONLINE_JUDGE
	fin = stdin;
	fout = stdout;
	#else
	fin = fopen("P6248.in", "rb");
	fout = fopen("P6248.out", "wb");
	#endif
	read(n, m);
	for (int i = 0; i < n; ++i) read(name, a[i]), ma[name] = i;//用map存下名字
	for (int i = 0; i < m; ++i) read(u, v, k[i]), gay[i] = (1 << ma[u]) | (1 << ma[v]);//将两个人绑在一起
	dfs(0, 0, 0, 0);
	write(ans);
	return 0;
}