灯 & 树-白红宇

灯 & 树

阅读量：7227 次

发布时间：2019-06-29

本文共 2187 字，大约阅读时间需要 7 分钟。

这回是两道题一起...

[USACO09NOV]灯

[中山市选2009]树

题意：给您一些灯，以及一些边。每次改变一盏灯的时候，它相邻的灯也会变。求把灯状态全部转换的最小操作次数。

解：

解异或方程组的经典题。

我们对于灯列一个方程组，如果i对j有影响就令a[j][i] = 1

然后解出上三角矩阵。

解出来a[i][i] = 1的地方就是确定的灯。

0就是可有可无的灯。

然后我们大暴力搜索可有可无的灯。遇到确定的灯就根据已经搜索的那些来确定。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 const int N = 40; 5  6 int n, p[N], ans = 0x3f3f3f3f; 7 std::bitset
         
           a[N]; 8  9 inline void Gauss() {10     for(int i = 1; i < n; i++) {11         for(int j = i; j <= n; j++) {12             if(a[j][i]) {13                 std::swap(a[i], a[j]);14                 break;15             }16         }17         if(!a[i][i]) {18             continue;19         }20         for(int j = i + 1; j <= n; j++) {21             if(a[j][i]) {22                 a[j] ^= a[i];23             }24         }25     }26     return;27 }28 29 inline void DFS(int k, int s) {30     if(s >= ans) {31         return;32     }33     if(k < 1) {34         ans = std::min(ans, s);35         return;36     }37     if(a[k][k]) {38         int t = a[k][n + 1];39         for(int i = k + 1; i <= n; i++) {40             if(a[k][i]) {41                 t ^= p[i];42             }43         }44         if(t) { /// need press45             p[k] = 1;46             DFS(k - 1, s + 1);47             p[k] = 0;48         }49         else {50             DFS(k - 1, s);51         }52     }53     else {54         DFS(k - 1, s);55         p[k] = 1;56         DFS(k - 1, s + 1);57         p[k] = 0;58     }59     return;60 }61 62 int main() {63     int m;64     scanf("%d%d", &n, &m);65     for(int i = 1, x, y; i <= m; i++) {66         scanf("%d%d", &x, &y);67         a[y].set(x);68         a[x].set(y);69     }70 71     for(int i = 1; i <= n; i++) {72         a[i].set(n + 1);73         a[i].set(i);74     }75 76     Gauss();77 78     DFS(n, 0);79 80     printf("%d", ans);81 82     return 0;83 }