首页 > 专题系列 > Java解POJ > POJ 1830 开关问题 [解题报告] Java
2013
11-10

POJ 1830 开关问题 [解题报告] Java

开关问题

问题描述 :

有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关,最多只能进行一次开关操作。你的任务是,计算有多少种可以达到指定状态的方法。(不计开关操作的顺序)

输入:

输入第一行有一个数K,表示以下有K组测试数据。

每组测试数据的格式如下:

第一行 一个数N(0 < N < 29)

第二行 N个0或者1的数,表示开始时N个开关状态。

第三行 N个0或者1的数,表示操作结束后N个开关的状态。

接下来 每行两个数I J,表示如果操作第 I 个开关,第J个开关的状态也会变化。每组数据以 0 0 结束。

输出:

如果有可行方法,输出总数,否则输出“Oh,it’s impossible~!!” 不包括引号

样例输入:

2
3
0 0 0
1 1 1
1 2
1 3
2 1
2 3
3 1
3 2
0 0
3
0 0 0
1 0 1
1 2
2 1
0 0

样例输出:

4
Oh,it's impossible~!!

温馨提示:

第一组数据的说明:

一共以下四种方法:

操作开关1

操作开关2

操作开关3

操作开关1、2、3 (不记顺序)

解题代码:

//* @author: 
/*高斯消元,然后根据消元后的矩阵得到答案,若有矛盾的行则无解

   否则解的个数为2^k   k为矩阵全为0的行数
 */



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class cin
{
static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int leave=0;
static int nextInt()throws IOException
{
   return Integer.parseInt(next());
}
static String next() throws IOException
{
   while(leave==0)
   {
    st=new StringTokenizer(in.readLine());
    leave=st.countTokens();
   }
   leave--;
   return st.nextToken();
}
static boolean hasNext() throws IOException
{
   while(leave==0)
   {
    String temp=in.readLine();
    if(temp==null)return false;
    st=new StringTokenizer(temp);
    leave=st.countTokens();
   }
   return true;
}
}

class Gaus 
{
    int a[][],num;
    static int M=2;
    Gaus(int m[][],int n)
    {
    a=m;
    num=n;
    }
    
    int mod(int a) //对M求余
    {
    return (a%M+M)%M;
    }
    
    void swap(int x,int y) //交换a[x],a[y]
    {
    int temp[];
    temp=a[x];
    a[x]=a[y];
    a[y]=temp;
    }
    
    void change() //矩阵变换
    {
    int i,j,k,max;
    for(i=0;i< num-1;i++)
    {
       max=i;
       for(j=i+1;j< num;j++)
       {
        if(a[j][i]>a[max][i])
         max=j;
       }
       if(a[max][i]==0)continue;
       swap(i,max);
       for(j=i+1;j< num;j++)
       {
        if(a[j][i]==0)continue;
        for(k=i+1;k<=num;k++)
        {
         a[j][k]=mod(a[j][k]*a[i][i]-a[i][k]*a[j][i]);
        }
        a[j][i]=0;
       }
    }
    }
    
    int noUse()//返回全为0的行数,若有不成立的行返回-1
    {
    int count=0,i,j;
    boolean zero;
    for(i=num-1;i>=0;i--)
    {
       zero=true;
       for(j=0;j< num;j++)
       {
        if(a[i][j]!=0)
        {
         zero=false;
         break;
        }
       }
       if(zero)
       {
        if(a[i][num]!=0)return -1;
        count++;
       }
    }
    return count;
    }
}

public class Main {
static int value[];
static void init()
{
   value=new int[29];
   value[0]=1;
   for(int i=1;i< 29;i++)
   {
    value[i]=2*value[i-1];
   }
}
    public static void main(String args[]) throws IOException
    {
    init();
    int a[][]=new int[28][29],t1,t2,t,n,i;
    int s1[]=new int[28];
    Gaus data;
    t=cin.nextInt();
    while((t--)>0)
    {
       n=cin.nextInt();
       for(i=0;i< n;i++)s1[i]=cin.nextInt();
       for(i=0;i< n;i++)
       {
        t1=cin.nextInt();
        Arrays.fill(a[i],0);
        a[i][i]=1;
        if(t1==s1[i])a[i][n]=0;
        else a[i][n]=1;
       }
       while(true)
       {
        t1=cin.nextInt();
        t2=cin.nextInt();
        if(t1==0&&t2==0)break;
        a[t2-1][t1-1]=1;
       }
       data=new Gaus(a,n);
       data.change();
       t1=data.noUse();
       if(t1< 0)System.out.println("Oh,it's impossible~!!");
       else System.out.println(value[t1]);
    }
    
    }
}

  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?