### 狗狗40题搞完纪念 » 1015

1015.cpp

```#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

inline int bin(int x) {
return 1 << x;
}

inline bool isbin(int x) {
return x > 0 && (x & (x - 1)) == 0;
}

#define V2E(i, j, k, a) do {\
v2e[i][j] = v2e[j][i] = a;\
v2e[i][k] = v2e[k][i] = a + 1;\
v2e[j][k] = v2e[k][j] = a + 2;\
} while (false)

const int MAXN = 18;

const int tri[] = {
7, 7 << 3, 7 << 6, 7 << 9, 7 << 12, 7 << 15,
bin(2) ^ bin(4) ^ bin(6),
bin(5) ^ bin(10) ^ bin(12),
bin(8) ^ bin(13) ^ bin(15),
};

int v2e[MAXN][MAXN];
int gao[1 << MAXN];

int newtri(int mask, int b) {
int ret = 0;
b = bin(b);
for (int i = 0; i < (int)(sizeof(tri) / sizeof(tri[0])); ++i) {
if ((tri[i] & b) == b && (mask & tri[i]) == (tri[i] ^ b)) {
++ret;
}
}
return ret;
}

void init() {
V2E(0, 1, 2, 0);
V2E(1, 3, 4, 3);
V2E(2, 4, 5, 6);
V2E(3, 6, 7, 9);
V2E(4, 7, 8, 12);
V2E(5, 8, 9, 15);
memset(gao, 0x88, sizeof(gao));
gao[(1 << MAXN) - 1] = 0;
for (int i = (1 << MAXN) - 1; i >= 0; --i) {
for (int j = 0; j < MAXN; ++j) {
if ((i & bin(j)) == 0) {
int k = newtri(i, j);
if (k > 0) {
gao[i] = max(gao[i], gao[i ^ bin(j)] + k);
} else {
gao[i] = max(gao[i], -gao[i ^ bin(j)]);
}
}
}
}
}

int main() {
bool first;
int re, n, m, x, y, d, mask;

init();
scanf("%d", &re);
for (int ri = 1; ri <= re; ++ri) {
if (ri > 1) {
puts("");
}
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &m);
first = true;
d = 0;
for (int j = 1; j <= m; ++j) {
scanf("%d%d", &x, &y);
--x;
--y;
x = v2e[x][y];
// fprintf(stderr, "x = %d; y = %d; mask = %o\n", x, y, mask);
if (y > 0) {
d += first ? y : -y;
} else {
first = !first;
}
}
// fprintf(stderr, "(d) = %d\n", d);