题目链接

题意

给出一个\(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

*/