CF226D The table

题目链接

题意

给出一个\(n\times m\)的矩阵，可以把某些行和某些列上面的数字变为相反数。问修改那些行和哪些列可以使得所有行和所有列之和都为非负数。

思路

每次将负数的行或者列变为相反数。因为矩阵上面的数字绝对值不超过\(100\)，而每改变一次，最少使得整个矩阵和\(+2\)，所以最多操作\(n\times m \times 100 = 10^6\)次。

代码

/*
* @author: wxyww
* @date: 2019-03-02 18:19:07
* @last modified time: 2019-03-02 18:54:53
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int n = 1100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,a[n][n],sum[2][n],ans[2][n];
void work1(int x) {
    sum[0][x] = -sum[0][x]; 
    for(int i = 1;i <= m;++i) {
        sum[1][i] -= a[x][i];
        sum[1][i] += -a[x][i];
        a[x][i] = -a[x][i];
    }
}
void work2(int x) {
    sum[1][x] = -sum[1][x];
    for(int i = 1;i <= n;++i) {
        sum[0][i] -= a[i][x];
        sum[0][i] += -a[i][x];
        a[i][x] = -a[i][x];
    }
}
int main() {
    n = read(),m = read();
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            a[i][j] = read();
            sum[0][i] += a[i][j];
            sum[1][j] += a[i][j];
        }
    }
    while(1) {
        int bz = 0;
        for(int i = 1;i <= n;++i) 
            if(sum[0][i] < 0) work1(i),bz = 1,ans[0][i] ^= 1;
        for(int i = 1;i <= m;++i) 
            if(sum[1][i] < 0) work2(i),bz = 1,ans[1][i] ^= 1;
        if(!bz) break;
    }
    int js = 0;
    for(int i = 1;i <= n;++i) js += ans[0][i];
    printf("%d ",js);
    for(int i = 1;i <= n;++i) if(ans[0][i]) printf("%d ",i);
    js = 0;
    for(int i = 1;i <= m;++i) js += ans[1][i];
    puts("");
    printf("%d ",js);
    for(int i = 1;i <= m;++i) if(ans[1][i]) printf("%d ",i);
    return 0;
}
/*
5 10
-2 -7 -10 -9 5 -9 -3 8 -8 5
3 0 9 8 -4 -3 -8 1 8 1
2 3 7 5 -8 -3 0 -9 -7 -2
-6 -7 0 0 6 9 -8 6 -8 3
7 9 -4 -5 -9 -3 8 6 -5 6
*/