P171SUMD – ptit

Đề bài:

• http://www.spoj.com/PTIT/problems/P171SUMD/

Thuật toán:

• Ưu tiên di chuyển hàng trước nếu m < n và ngược lại.
• Sử dụng thuật toán tham lam trừ từng hàng và từng từng cột.

Code:

• C++ (xem)

#include 
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector VI;
typedef long long ll;
typedef pair PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 200;
const int oo = 1000;
int m, n, i, j, g[MAXN][MAXN], kt, mi, tam, dadoi;
vector H, C;

void xulyhang() {
    for (int i=1; i<=m; i++) {
        mi = oo;
        for (int j=1; j<=n; j++) mi = min(mi, g[i][j]);
        for (int j=1; j<=mi; j++) H.push_back(i);
        for (int j=1; j<=n; j++) g[i][j]-=mi;
    }
}

void xulycot() {
    for (int j=1; j<=n; j++) {
        mi = oo;
        for (int i=1; i<=m; i++) mi = min(mi, g[i][j]);
        for (int i=1; i<=mi; i++) C.push_back(j);
        for (int i=1; i<=m; i++) g[i][j]-=mi;
    }
}

int main() {
    cin >> m >> n;
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++) cin >> g[i][j];
    kt = 1;
    if (m < n) {
        xulyhang();
        xulycot();
    }
    else {
        xulycot();
        xulyhang();
    }
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++)
        if (g[i][j]!=0) kt = 0;
    if (kt==0) cout << -1;
    else {
            cout << C.size()+H.size() << endl;
            for (int i=0; i