Submission #70008973

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int N;
int next[16];
int A[16][16];
int memo[1 << 16];
int calc(int status) {
  int num = 0;
  int next_candidate = 0;
  int ans = 0;
  int i;
  /* N部屋埋まっている場合、下のループでcalcを呼び出さないので、チェックなしでおｋ */
  if (memo[status]) return ~memo[status];
  for (i = 0; i < N; i++) {
    if ((status >> i) & 1) {
      num++;
      next_candidate |= next[i];
    }
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int N;
int next[16];
int A[16][16];

int memo[1 << 16];

int calc(int status) {
	int num = 0;
	int next_candidate = 0;
	int ans = 0;
	int i;
	/* N部屋埋まっている場合、下のループでcalcを呼び出さないので、チェックなしでおｋ */
	if (memo[status]) return ~memo[status];
	for (i = 0; i < N; i++) {
		if ((status >> i) & 1) {
			num++;
			next_candidate |= next[i];
		}
	}
	next_candidate &= ~status;
	for (i = 0; i < N; i++) {
		if ((next_candidate >> i) & 1) {
			int candidate = calc(status | (1 << i)) + A[num][i];
			if (candidate > ans) ans = candidate;
		}
	}
	return ~(memo[status] = ~ans);
}

int main(void) {
	int M;
	int i, j;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		int U, V;
		if (scanf("%d%d", &U, &V) != 2) return 1;
		next[U - 1] |= 1 << (V - 1);
		next[V - 1] |= 1 << (U - 1);
	}
	for (i = 1; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (scanf("%d", &A[i][j]) != 1) return 1;
		}
	}
	printf("%d\n", calc(1));
	return 0;
}

Submission Info

Judge Result