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

#include<cstring>
#include<iostream>
#include<cstdio>

using namespace std;
int n,m,s;
int vera[25],verp[25],p[25],last[25],a[25][25],f[1<<21];


void add(int ff,int pp,int aa){
	verp[++s]=pp;
	vera[s]=aa;
	last[s]=p[ff];
	p[ff]=s;
}

int lowbit(int x){
	return x&(-x);
}
int count(int x){
	int ans=0;
	while (x){
		ans++;
		x-=lowbit(x);
	}
	return ans;
}

void work(){
	int i,j,k,temp;
	memset(f,0,sizeof(f));
	for (i=1;i<(1<<n);i++){
		k=count(i);
		for (j=1;j<=n;j++)
		 if (i & (1<<(j-1))){
			f[i]=max(f[i],f[i-(1<<(j-1))]+a[j][k]);
		}
		temp=0;
		for (j=p[k];j;j=last[j]){
			if (f[i]>=verp[j]) temp+=vera[j];
		}
		f[i]+=temp;
	}
}
int main(){
	freopen("deca.in","r",stdin);
	freopen("deca.out","w",stdout);
	int i,j,k,pp,aa;
	s=0;
	memset(p,0,sizeof(p));
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&k,&pp,&aa);
		add(k,pp,aa);
	}
	for (i=1;i<=n;i++) 
	 for (j=1;j<=n;j++){
	 	scanf("%d",&a[i][j]);
	 }
	work();
	cout<<f[(1<<n)-1]<<endl;
}