BZOJ 1770: [Usaco2009 Nov]lights 燈

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int MAXN = 105;
 6 
 7 int N, M, G[MAXN][MAXN], ANS, TMP[MAXN];
 8 
 9 void READ(void)
10 {
11     scanf("%d%d", &N, &M);
12     
13     for (int i = 1; i <= N; ++i)
14         G[i][i] = G[i][N + 1] = true;
15     
16     for (int i = 1, x, y; i <= M; ++i)
17     {
18         scanf("%d%d", &x, &y);
19         G[x][y] = G[y][x] = true; 
20     }
21 }
22 
23 void GAUSS(void)
24 {
25     for (int i = 1, j, k; i <= N; ++i)
26     {
27         for (j = i; j <= N && !G[j][i]; ++j);
28         
29         if (j <= N)
30         {
31             if (i != j)
32             {
33                 for (k = 1; k <= N + 1; ++k)
34                     swap(G[i][k], G[j][k]); 
35             }
36             if (G[i][i])
37             {
38                 for (j = 1; j <= N; ++j)
39                     if (i != j && G[j][i])
40                         for (k = 1; k <= N + 1; ++k)
41                             G[j][k] ^= G[i][k];
42             }
43         }
44     }
45 }
46 
47 void DFSANS(int t, int cnt)
48 {
49     if (cnt >= ANS)
50         return;
51     if (t == 0)
52         ANS = min(ANS, cnt);
53     else
54     {
55         if (G[t][t])
56         {
57             TMP[t] = G[t][N + 1];
58             for (int i = N; i > t; --i)
59                 if (G[t][i])TMP[t] ^= TMP[i];
60             DFSANS(t - 1, cnt + TMP[t]);
61         }
62         else
63         {
64             TMP[t] = 0; DFSANS(t - 1, cnt);
65             TMP[t] = 1; DFSANS(t - 1, cnt + 1);
66         }
67     }
68 }
69 
70 void PUTANS(void)
71 {
72     ANS = 2e9;
73     DFSANS(N, 0);
74     printf("%d\n", ANS);
75 }
76 
77 signed main(void)
78 {
79     READ();    
80     GAUSS();
81     PUTANS();
82 }

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 typedef long long LL;
 6 
 7 const int N = 40;
 8 const int M = 2000;
 9 
10 int n, m;
11 
12 int tot;
13 int hd[N];
14 int to[M];
15 int nt[M];
16 
17 int ans;
18 
19 map<LL, int> MAP;
20 
21 void insert(LL bit, int cost)
22 {
23     if (MAP.count(bit))
24         MAP[bit] = min(MAP[bit], cost);
25     else
26         MAP[bit] = cost;
27 }
28 
29 void DFS1(int t, LL bit, int cost)
30 {
31     if (t > n / 2)
32     { insert(bit, cost); return; }
33     
34     DFS1(t + 1, bit, cost);
35     
36     bit ^= (1LL << (t - 1));
37     
38     for (int i = hd[t]; ~i; i = nt[i])
39         bit ^= (1LL << (to[i] - 1));
40         
41     DFS1(t + 1, bit, cost + 1);
42 }
43 
44 int query(LL bit)
45 {
46     if (MAP.count(bit))
47         return MAP[bit];
48     else
49         return -1;
50 }
51 
52 void DFS2(int t, LL bit, int cost)
53 {
54     if (t > n)
55     {
56         int ret = query(((1LL << n) - 1) ^ bit);
57         if (ret != -1)ans = min(ans, cost + ret);
58         return;
59     }
60     
61     DFS2(t + 1, bit, cost);
62     
63     bit ^= (1LL << (t - 1));
64     
65     for (int i = hd[t]; ~i; i = nt[i])
66         bit ^= (1LL << (to[i] - 1));
67         
68     DFS2(t + 1, bit, cost + 1);
69 }
70 
71 signed main(void)
72 {
73     scanf("%d%d", &n, &m);
74     
75     memset(hd, -1, sizeof(hd));
76     
77     for (int i = 1; i <= m; ++i)
78     {
79         int x, y; scanf("%d%d", &x, &y);
80         nt[tot] = hd[x]; to[tot] = y; hd[x] = tot++;
81         nt[tot] = hd[y]; to[tot] = x; hd[y] = tot++;
82     }
83     
84     ans = 2e9;
85     DFS1(1, 0LL, 0);
86     DFS2(n / 2 + 1, 0LL, 0);
87     
88     printf("%d\n", ans);
89 }