DZY 's BLOG

经典的开关问题的树上的版本。

还是赤果果的高斯消元。

多了一个细节是求出sigma(x[i])的最小值。

先跑高斯消元。得到倒三角矩阵之后。考虑到n=100。而且不确定位应该不会太多。（不然怎么过啊哦擦）。所以可以把每种解都跑出来。保留最小值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int a[110][110],x[110],n,An = 1000000009;
void dfs(int k,int sum){
    if(sum >= An) return;
    if(k == 0){
        An = min(An,sum);
        return;
    }
    if(a[k][k]){
        int p = a[k][n + 1];
        for(int i = k + 1;i <= n;i ++)
            if(a[k][i]) p ^= x[i];
        x[k] = p;
        if(x[k])    dfs(k - 1,sum + 1);
        else    dfs(k - 1,sum);
    }else{
        x[k] = 0;
        dfs(k - 1,sum);
        x[k] = 1;
        dfs(k - 1,sum + 1);
        x[k] = 0;
    }
}        
void solve(){
    for(int k = 1;k <= n;k ++){
        int f = 0;
        for(int i = k;i <= n;i ++)
            if(a[i][k]){
                for(int j = 1;j <= n + 1;j ++)  swap(a[i][j],a[k][j]);
                f = 1;
                break;
            }
        if(!f)  continue;
        for(int i = k + 1;i <= n;i ++)  if(a[i][k])
            for(int j = 1;j <= n + 1;j ++)  a[i][j] ^= a[k][j];
    }
    An = 1000000009;
    dfs(n,0);
    cout << An << endl;
}
int main(){
    while(scanf("%d",&n),n){
        int u,v;
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        for(int i = 1;i < n;i ++){
            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;
        solve();
    }
    return 0;
}