【bzoj2466】[中山市选2009]树

2015.04.15 10:14 Wed | 5次阅读 | 旧日oi | 固定链接 | 源码

Description

图论中的树为一个无环的无向图。给定一棵树,每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了,那么该节点的灯会从熄灭变为点亮(当按之前是熄灭的),或者从点亮到熄灭(当按之前是点亮的)。并且该节点的直接邻居也发生同样的变化。
开始的时候,所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。

Input

输入文件有多组数据。
输入第一行包含一个整数n,表示树的节点数目。每个节点的编号从1到n。
输入接下来的n – 1行,每一行包含两个整数x,y,表示节点x和y之间有一条无向边。
当输入n为0时,表示输入结束。

Output

对于每组数据,输出最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。每一组数据独占一行。

Sample Input

3
1 2
1 3
0

Sample Output

1

HINT

对于100%的数据,满足1 <= n <=100。

题解

高斯消元解异或方程组,很好的模板

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[105][105],ans,x[105];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int sure[105];
int gauss(int equ,int var)
{
    int i,id,j,k;
    for(i=1,id=1;i<=var;i++,id++)
    {
        for(j=id;j<=equ&&!a[j][i];j++);
        if(j>equ) {id--;continue;}
        sure[id]=i;
        if(j!=id) for(k=1;k<=var+1;k++) swap(a[j][k],a[id][k]);
        for(j=id+1;j<=equ;j++) if(a[j][i]) for(k=i;k<=var+1;k++) 
            a[j][k]^=a[id][k];
    }
    for(j=id;j<=equ;j++) if(a[j][var+1]) return -1;
    return id-1;
}
void dfs(int cur,int now,int ret)
{
    if(cur<1)
    {
        ans=min(ans,ret);
        return;
    }
    if(ret>=ans) return;
    if(now==sure[cur]) 
    {
        bool tmp=a[cur][n+1];
        for(int i=now+1;i<=n;i++) tmp^=a[cur][i]*x[i];
        x[now]=tmp;
        dfs(cur-1,now-1,ret+x[now]);
    }
    else
    {
        x[now]=0;dfs(cur,now-1,ret);
        x[now]=1;dfs(cur,now-1,ret+1);
    }
}
int main()
{
    while(cin>>n&&n)
    {
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        memset(sure,0,sizeof(sure));
        ans=0x3f3f3f3f;
        for(int u,v,i=1;i<n;i++)
        {
            u=read();v=read();
            a[u][v]=a[v][u]=1;
        }
        for(int i=1;i<=n;i++)
        a[i][i]=a[i][n+1]=1;
        int t=gauss(n,n);
        if(t==-1) puts("inf");
        else
        {
            dfs(t,n,0);
            cout<<ans<<endl;
        }
    }
    return 0;
}```