uva11082 Matrix Decompressing

网络流

首先算出每行每列的数的和。

每行的值减去c，每列的值减去R

然后每行和每列之间连边，容量为19.

这样一来，(i,j)的流量相当于(i,j)的值-1.

这样就避免了流量为0不对应答案的尴尬情况。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn = 1000 + 10;

const int maxm = 100000 + 10;

const int inf = 0x3f3f3f3f;

int g[maxn],v[maxm],nex[maxm],f[maxm],eid;

int gap[maxn],d[maxn],vid;

int n,m,S,T;

int a[maxn],b[maxn];

int res[maxn][maxn];

void addedge(int a,int b,int F) {

    v[eid]=b; f[eid]=F; nex[eid]=g[a]; g[a]=eid++;

    v[eid]=a; f[eid]=0; nex[eid]=g[b]; g[b]=eid++;

}

void build() {

    memset(a,0,sizeof(a));

    memset(b,0,sizeof(b));

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=n;i>=1;i--) a[i]-=a[i-1];

    for(int i=n+1;i<=n+m;i++) scanf("%d",&b[i]);

    for(int i=n+m;i>=n+1;i--) b[i]-=b[i-1];

    memset(g,-1,sizeof(g)); eid=0;

    S=n+m+1; T=n+m+2; vid=n+m+2;

    for(int i=1;i<=n;i++) {

        addedge(S,i,a[i]-m);

    }

    for(int i=n+1;i<=n+m;i++) {

        addedge(i,T,b[i]-n);

    }

    for(int i=1;i<=n;i++)

    for(int j=n+1;j<=n+m;j++) {

        addedge(i,j,19);

    }

}

int ISAP(int u,int flow) {

    if(u==T) return flow;

    int cur=0,aug,mindist=vid;

    for(int i=g[u];~i;i=nex[i]) if(f[i] && d[u]==d[v[i]]+1) {

        aug=ISAP(v[i],min(flow-cur,f[i]));

        cur+=aug;

        f[i]-=aug;

        f[i^1]+=aug;

        if(cur==flow || d[S]>=vid) return cur;

    }

    if(cur==0) {

        if(!--gap[d[u]]) {

            d[S]=vid;

            return cur;

        }

        for(int i=g[u];~i;i=nex[i]) if(f[i])

            mindist=min(mindist,d[v[i]]);

        ++gap[d[u]=mindist+1];

    }

    return cur;

}

void solve() {

    memset(d,0,sizeof(d));

    memset(gap,0,sizeof(gap));

    gap[0]=vid;

    while(d[S]<vid) {

        ISAP(S,inf);

    }

    for(int u=1;u<=n;u++) {

        for(int i=g[u];~i;i=nex[i]) res[u][v[i]]=20-f[i];

    }

    for(int i=1;i<=n;i++) {

        for(int j=n+1;j<n+m;j++)

            printf("%d ",res[i][j]);

        printf("%d\n",res[i][n+m]);

    }

}

int main() {

    int T;

    scanf("%d",&T);

    for(int i=1;i<=T;i++) {

        if(i>1) printf("\n");

        printf("Matrix %d\n",i);

        build();

        solve();

    }

    return 0;

}