UVA11082

最大ストリームの問題だが...i行目からj列目までの最大ストリームは、(i,j)要素で、弱すぎて、思いもよらなかったでしょう.
同時にノードのcapを計算する場合,1~20の範囲は0~19に変換され,行ごとの値からcを減算し,列ごとの値からrを減算する.

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x7fffffff;
struct Edge
{
    int from,to,flow,cap;
    Edge(int u,int v,int f,int c):from(u),to(v),flow(f),cap(c){}
};
vector<Edge> edges;
vector<int> num[45];
int a[45],p[45];
int r,c,sumr[21],sumc[21],vr[21],vc[21],k;
int map[21][21];
void add(int from,int to,int cap)
{
    edges.push_back(Edge(from,to,0,cap));
    edges.push_back(Edge(to,from,0,0));
    k+=2;
    num[from].push_back(k-2);
    num[to].push_back(k-1);
}
void maxflow(int s,int t)
{
    int x,i;
    while(true)
    {
        memset(a,0,sizeof(a));
        queue<int> q;
        q.push(s);
        a[s]=INF;
        while(!q.empty())
        {
            x=q.front(),q.pop();
            for(i=0;i<num[x].size();i++)
            {
                Edge &e=edges[num[x][i]];
                if(!a[e.to]&&e.cap>e.flow)
                {
                    a[e.to]=min(a[x],e.cap-e.flow);
                    p[e.to]=num[x][i];
                    q.push(e.to);
                }
            }
            if(a[t]) break;
        }
        if(!a[t]) break;
        for(i=t;i!=s;i=edges[p[i]].from)
        {
            edges[p[i]].flow+=a[t];
            edges[p[i]^1].flow-=a[t];
        }
    }
}
void output()
{
    int i,j;
    for(i=1;i<=r;i++)
        for(j=1;j<num[i].size();j++)
        map[i][j]=edges[num[i][j]].flow;
    for(i=1;i<=r;i++)
    {
        for(j=1;j<=c;j++) cout<<map[i][j]+1<<" ";
        cout<<endl;
    }
    cout<<endl;
}
int main()
{
    int T,cnt=0,i,j;
    sumr[0]=sumc[0]=0;
    scanf("%d",&T);
    while(T--)
    {
        edges.clear();
        for(i=0;i<45;i++) num[i].clear();
        k=0;
        scanf("%d%d",&r,&c);
        for(i=1;i<=r;i++)
        {
            scanf("%d",&sumr[i]);
            vr[i]=sumr[i]-sumr[i-1]-c;
            add(0,i,vr[i]);
        }
        for(i=1;i<=c;i++)
        {
            scanf("%d",&sumc[i]);
            vc[i]=sumc[i]-sumc[i-1]-r;
            add(r+i,c+r+1,vc[i]);
        }
        for(i=1;i<=r;i++)
            for(j=1;j<=c;j++)
            {
                add(i,j+r,19);
            }
        maxflow(0,r+c+1);
        printf("Matrix %d
",++cnt);
        output();
    }
}