POJ3185高斯消元

The Water Bowls

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3372		Accepted: 1315

The cows have a line of 20 water bowls from which they drink. The bowls can be either right-side-up (properly oriented to serve refreshing cool water) or upside-down (a position which holds no water). They want all 20 water bowls to be right-side-up and thus use their wide snouts to flip bowls. 

Their snouts, though, are so wide that they flip not only one bowl but also the bowls on either side of that bowl (a total of three or -- in the case of either end bowl -- two bowls). 

Given the initial state of the bowls (1=undrinkable, 0=drinkable -- it even looks like a bowl), what is the minimum number of bowl flips necessary to turn all the bowls right-side-up?

Line 1: A single line with 20 space-separated integers

Line 1: The minimum number of bowl flips necessary to flip all the bowls right-side-up (i.e., to 0). For the inputs given, it will always be possible to find some combination of flips that will manipulate the bowls to 20 0's.

0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0

3

Explanation of the sample: 

Flip bowls 4, 9, and 11 to make them all drinkable: 
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [initial state] 
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 4] 
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 9] 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [after flipping bowl 11]

 

題解：

這題也是聯動問題 與POJ1222相似 點擊打開鏈接POJ1222

隻是構造增廣陣的方式不通 按照高消+DFS模板就可以過

 

#include <iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=230;
int a[maxn][maxn+1],x[maxn];//a 是係數矩陣和增廣矩陣，x 是最後存放的解
// a[][maxn]中存放的是方程右麵的值（bi）
int equ,var;//equ 是係數陣的行數，var 是係數矩陣的列數（變量的個數）
int free_num,ans=100000000;

int abs1(int num) //取絕對值
{
    if (num>=0) return num;
    else
        return -1*num;
}
void Debug(void)
{
    int i, j;
    for (i = 0; i < equ; i++)
    {
        for (j = 0; j < var + 1; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
//調試輸出，看消元後的矩陣值，提交時，就不用了
inline int gcd(int a, int b) //最大公約數
{
    int t;
    while (b != 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

inline int lcm(int a, int b) //最小公倍數
{
    return a * b / gcd(a, b);
}

int dfs(int p) //枚舉自由解，隻能取0-1，枚舉完就回帶，找到最小的
{
    if (p<=free_num-1) //深入到了主對角線元素非0 的行了
    {
        //下麵就是回帶的代碼啊
        for(int i = free_num-1; i >= 0; --i)
        {
            int tmp = a[i][var] % 2;
            for(int j = i+1; j < var; ++j) //x[i]取決於x[i+1]--x[var]啊，所以後麵的解對前麵的解有影
//響。
                if(a[i][j] != 0)
                    tmp = ( tmp - (a[i][j]*x[j])%2 + 2 ) % 2;
            x[i] = (tmp/a[i][i]) % 2; //上麵的正常解
        } //回帶完成了
//計算解元素為1 的個數；
        int sum=0;
        for(int i=0; i<var; i++) sum+=x[i];
        if (ans>sum) ans=sum;
        return 0;
    }
    x[p]=0;
    dfs(p-1);
    x[p]=1;
    dfs(p-1);
}
void swap(int &a,int &b)
{
    int temp=a;    //交換 2 個數
    a=b;
    b=temp;
}
int Gauss()
{
    int k,col = 0;
//當前處理的列
    for(k = 0; k < equ && col < var; ++k,++col)
    {
        int max_r = k;
        for(int i = k+1; i < equ; ++i)
            if(a[i][col] > a[max_r][col])
                max_r = i;
        if(max_r != k)
        {
            for(int i = k; i < var + 1; ++i)
                swap(a[k][i],a[max_r][i]);
        }
        if(a[k][col] == 0)
        {
            k--;
            continue;
        }
        for(int i = k+1; i < equ; ++i)
        {
            if(a[i][col] != 0)
            {
                int LCM = lcm(a[i][col],a[k][col]);
                int ta = LCM/a[i][col], tb = LCM/a[k][col];
                if(a[i][col]*a[k][col] < 0)
                    tb = -tb;
                for(int j = col; j < var + 1; ++j)
                    a[i][j] = ( (a[i][j]*ta)%2 - (a[k][j]*tb)%2 + 2 ) % 2;
                // 0 和 1 兩種狀態
            }
        }
    }
//a[i][j]隻有

//上述代碼是消元的過程，行消元完成
//解下來 2 行，判斷是否無解
//注意 K 的值，k 代表係數矩陣值都為 0 的那些行的第 1 行
    for(int i = k; i < equ; ++i)
        if(a[i][col] != 0)
            return -1;
//Debug();

//唯一解或者無窮解,k<=var
//var-k==0 唯一解；var-k>0 無窮多解，自由解的個數=var-k
//能執行到這，說明肯定有解了，無非是 1 個和無窮解的問題。
//下麵這幾行很重要，保證秩內每行主元非 0，且按對角線順序排列，就是檢查列
    for(int i = 0; i <equ; ++i)//每一行主元素化為非零
        if(!a[i][i])
        {
            int j;
            for(j = i+1; j<var; ++j)
                if(a[i][j])
                    break;
            if(j == var)
                break;
            for(int k = 0; k < equ; ++k)
                swap(a[k][i],a[k][j]);
        }
// ----處理保證對角線主元非 0 且順序，檢查列完成

    free_num=k;
    if (var-k>0)
    {
        dfs(var-1);
        return ans;
        //無窮多解，先枚舉解，然後用下麵的回帶代碼進行回帶；
//這裏省略了下麵的回帶的代碼；不管唯一解和無窮解都可以回帶，隻不過無窮解
//回帶時，默認為最後幾個自由變元=0 而已。
    }
    if(var-k<0)
        return -1;
// 無解返回 -1
    if (var-k==0)//唯一解時
    {
//下麵是回帶求解代碼，當無窮多解時，最後幾行為 0 的解默認為 0；
        for(int i = k-1; i >= 0; --i) //從消完元矩陣的主對角線非 0 的最後 1 行，開始往
//回帶
        {
            int tmp = a[i][var] % 2;

            for(int j = i+1; j < var; ++j) //x[i]取決於 x[i+1]--x[var]啊，所以後麵的解對前麵的解有影響。
                if(a[i][j] != 0)
                    tmp = ( tmp - (a[i][j]*x[j])%2 + 2 ) % 2;
            //if (a[i][i]==0) x[i]=tmp;//最後的空行時，即無窮解得
            //else
            x[i] = (tmp/a[i][i]) % 2; //上麵的正常解
        }
        int sum=0;
        for(int i=0; i<var; i++)
            sum+=x[i];
        return sum;

        //回帶結束了
    }
}

int main()
{
    int map[22];
    equ=var=20;
    while(scanf("%d",&map[0])!=EOF)
    {
        for(int i=1; i<20; i++)
            scanf("%d",&map[i]);
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        for(int i=0; i<20; i++)
        {

            a[i][i]=1;
            if(i>0)
                a[i][i-1]=1;
            if(i<19)
                a[i][i+1]=1;
            if(map[i])
                a[i][20]=1;
        }
        int j1=Gauss();
        printf("%d\n",j1);
    }
    return 0;
}