1、题目大意:给你一棵树,树的每个节点都有一个权值,是0或1,最开始都是0,你可以做一种修改操作,就是把一个节点和它相邻的
节点的权值取反,问最少几次修改能把所有节点的权值变得都是1,最多100个节点
2、分析:经典高斯消元问题,如果i节点的修改能够影响到j节点,那么a[i][j] = 1;(a是系数矩阵)
等式的右边是1。。。对于所有的*元2^n暴力枚举,然后就AC了, 这题坑了一个礼拜啊,(大神们不要嘲笑我T_T)
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; int a[110][110], is_free[110], p[110], ans[110], end_ans, m, tot; inline void gauss_elimination(int n){ for(int i = 1, j = 1; i <= n; i ++, j ++){ if(j == n + 1){ m = i - 1; return; } for(int k = i; k <= n; k ++){ if(a[k][j]){ for(int h = 1; h <= n + 1; h ++) swap(a[i][h], a[k][h]); break; } } if(!a[i][j]){ is_free[j] = 1; tot ++; i --; continue; } for(int k = i + 1; k <= n; k ++){ if(a[k][j]){ for(int h = j; h <= n + 1; h ++){ a[k][h] ^= a[i][h]; } } } } m = n; return; } int main(){ int n; while(scanf("%d", &n) != EOF){ if(n == 0) return 0; memset(a, 0, sizeof(a)); memset(is_free, 0, sizeof(is_free)); memset(ans, 0, sizeof(ans)); tot = 0; end_ans = 2147483647; for(int i = 1; i < n; i ++){ int u, v; scanf("%d%d", &u, &v); a[u][v] = a[v][u] = 1; } for(int i = 1; i <= n; i ++) a[i][i] = a[i][n + 1] = 1; gauss_elimination(n); for(int i = 0; i < (1 << tot); i ++){ for(int j = 0; j < tot; j ++){ if(i & (1 << j)) p[j + 1] = 1; else p[j + 1] = 0; } int u = 0; for(int j = 1; j <= n; j ++){ if(is_free[j]){ u ++; ans[j] = p[u]; } } for(int k = n, j = m; j >= 1; j --){ for( ; k && is_free[k]; k --); ans[k] = a[j][n + 1]; for(int h = k + 1; h <= n; h ++){ if(a[j][h]) ans[k] ^= ans[h]; } k --; } int cnt = 0; for(int j = 1; j <= n; j ++) if(ans[j]) cnt ++; end_ans = min(end_ans, cnt); } printf("%d\n", end_ans); } return 0; }