poj 1681 Painter's Problem(高斯消元)

id=1681">http://poj.org/problem?

id=1681

求最少经过的步数使得输入的矩阵全变为y。



思路:高斯消元求出*变元。然后枚举*变元,求出最优值。

注意依据*变元求其它解及求最优值的方法。



#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#define LL long long
#define _LL __int64 using namespace std;
const int INF = 0x3f3f3f3f; char mapp[17][17];
int a[16*16][16*16];
int equ,var;
int x[16*16];
int free_x[16*16]; //保存*变元,枚举求最优解
int free_num; void init()
{
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
} void debug()
{
for(int i = 0; i < equ; i++)
{
for(int j = 0; j < var+1; j++)
printf("%d",a[i][j]);
printf("\n");
}
} int Gauss()
{
int row,col,i,j;
int max_r; row = col = 0;
free_num = 0;
while(row < equ && col < var)
{
max_r = row;
for(i = row+1; i < equ; i++)
{
if( abs(a[i][col]) > abs(a[max_r][col]) )
max_r = i;
} if(max_r != row)
{
for(j = col; j < var+1; j++)
swap(a[max_r][j],a[row][j]);
}
if(a[row][col] == 0)
{
free_x[ free_num++ ] = col; //该列相应的变量是*元
col++;
continue;
} for(i = row+1; i < equ; i++)
{
if(a[i][col] == 0) continue;
for(j = col; j < var+1; j++)
a[i][j] ^= a[row][j];
}
row++;
col++;
} for(i = row; i < equ; i++)
if(a[i][col] != 0)
return -1; //无解 if(row < var)
return var-row; //返回*变元的数目 for(i = var-1; i >= 0; i--) //有唯一解
{
x[i] = a[i][var];
for(j = i+1; j < var; j++)
x[i] ^= (a[i][j] && x[j]);
}
return 0;
} void solve()
{
int t = Gauss();
if(t == -1)
{
printf("inf\n");
return;
}
else if(t == 0)
{
int ans = 0;
for(int i = 0; i < var; i++)
ans += x[i];
printf("%d\n",ans);
return;
}
else
{
int ans = INF;
int sta = (1<<t); //t个变量共同拥有sta个基础解
int cnt; for(int i = 0; i < sta; i++)
{
cnt = 0;
//先给*变元赋值
for(int j = 0; j < t; j++)
{
if((1<<j) & i)
{
x[ free_x[j] ] = 1;
cnt++;
}
else
x[ free_x[j] ] = 0;
}
//求出其它的解
for(int j = var-t-1; j >= 0; j--)
{
int l,k; for(k = j; k < var; k++)
if(a[j][k])
break; //先找到该行第一个不为0的数
x[k] = a[j][var]; for(l = k+1; l < var; l++)
x[k] ^= (x[l] && a[j][l]);
cnt += x[k];
} ans = min(ans,cnt);
}
printf("%d\n",ans);
return;
}
} int main()
{
int n,test; scanf("%d",&test);
while(test--)
{
init();
scanf("%d",&n); equ = var = n*n; for(int i = 0; i < n; i++)
scanf("%s",mapp[i]); for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(mapp[i][j] == 'w')
a[i*n+j][var] = 1;
else a[i*n+j][var] = 0;
}
}
for(int i = 0; i < equ; i++)
{
int x = i/n;
int y = i%n; for(int j = 0; j < var; j++)
{
int xx = j/n;
int yy = j%n;
if( abs(x-xx) + abs(y-yy) <= 1)
a[i][j] = 1;
else a[i][j] = 0;
}
}
solve();
}
return 0;
}







上一篇:SQL SERVER Transactional Replication中添加新表如何不初始化整个快照


下一篇:POJ 1681 Painter's Problem (高斯消元 枚举*变元求最小的步数)