记录编号	96709	评测结果	AAAAAAAAAA
题目名称	[USACO Feb14] 奶牛的十项全能	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.675 s
提交时间	2014-04-14 16:19:03	内存使用	8.32 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
#define N 21
int f[(1 << N) + 5];//f[i] = max(f[i],f[(i ^ (1 << j))] + s[j][popcount(i)])
//f[i] += temp;
//temp += reward[popcount(i)][k].a (reward[popcount(i)][k].p <= f[i] )
int s[N][N];
int n,b;
struct arr{
	int num,p[N],a[N];
	arr(){
		num  = 0;
		memset(p,0,sizeof(p));
		memset(a,0,sizeof(a));
	}
}reward[N];

inline int lowbit(int x){
	return x & (-x);
}

int popcount(int x){
	int ans = 0;
	for (int i = x; i > 0; i -= lowbit(i)) ans ++;
	return ans;
}
inline bool pd(int x,int y){
	return x & (1 << (y - 1));
}
int main(){
		freopen("deca.in","r",stdin);	
	freopen("deca.out","w",stdout);	
	scanf("%d%d",&n,&b);
	int x,y,z;
	for (int i = 1; i <= b; i++){
		scanf("%d%d%d",&x,&y,&z);
		reward[x].a[++reward[x].num] = z;
		reward[x].p[reward[x].num] = y;
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++){
			scanf("%d",&s[i][j]);
		}
	f[0] = 0;
	for (int i = 1; i < (1 << n); i++){
		int pos = popcount(i);
		for (int j = 1; j <= n; j++){
			if (pd(i,j)){
				f[i] = max(f[i],f[i ^ (1 << (j - 1))] + s[j][pos]);
			}
		}
		int tem = 0;
		for (int j = 1; j <= reward[pos].num; j++){
			if (reward[pos].p[j] <= f[i]) tem += reward[pos].a[j];
		}
		f[i] += tem;
	}
	printf("%d\n",f[(1 << n) - 1]);
}