Matrix Decompressing

题目：

   给出一个矩阵的前i行，前j列的和。要求你求出满足的矩阵。

矩阵的数范围在[1,20]。

  一開始就坑在了这里。没读细致题目。

囧。。。

  事实上这题的模型就是一个网络流的行列模型，跟poj的那题budge一样建图。只是Poj 的那个建图输入麻烦。而这题是裸的，由于已经告诉你了下界为1，上界为20，囧。。。并且poj那题我至今也不知道为什么我会一直超时。

T_T

算法:

   行列模型能够转换成网络流的有源汇上下界网络流求解。而行号和列号分别作为顶点。

连结超级源汇点就ok了。跑两边最大流，而每条边上的流量+下界流就是结果了。

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <cstdio>

#include <cstring>

using namespace std;

const int INF = 1 << 20;

const int MAXN = 400 + 10;

struct Edge{

   int from,to,cap,flow;

   Edge(){};

   Edge(int _from,int _to,int _cap,int _flow)

      :from(_from),to(_to),cap(_cap),flow(_flow){};

};

vector<Edge> edges;

vector<int> G[MAXN];

int cur[MAXN],d[MAXN];

int N,M,src,sink,ss,tt;

//////////////////////////////////////

int ans[MAXN][MAXN];

void init(){

   ss = N + M + 2;   tt = ss + 1;

   src = tt + 1; sink = src + 1;

   for(int i = 0;i <= sink + 1;++i)

     G[i].clear();

   edges.clear();

}

void addEdge(int from,int to,int cap){

   edges.push_back(Edge(from,to,cap,0));

   edges.push_back(Edge(to,from,0,0));

   int sz = edges.size();

   G[from].push_back(sz - 2);

   G[to].push_back(sz - 1);

}

bool BFS(){

   fill(d,d + sink + 2,-1);

   queue<int> Q;

   Q.push(src);

   d[src] = 0;

   while(!Q.empty()){

       int x = Q.front(); Q.pop();

       for(int i = 0;i < (int)G[x].size();++i){

           Edge& e = edges[G[x][i]];

           if(d[e.to] == -1 && e.cap > e.flow){

               d[e.to] = d[x] + 1;

               Q.push(e.to);

           }

       }

   }

   return d[sink] > 0;

}

int DFS(int x,int a){

    if(x == sink || a == 0)

         return a;

    int flow = 0,f;

    for(int& i = cur[x];i < (int)G[x].size();++i){

        Edge& e = edges[G[x][i]];

        if(d[e.to] == d[x] + 1 && (f = DFS(e.to,min(a,e.cap - e.flow))) > 0){

            e.flow += f;

            edges[G[x][i]^1].flow -= f;

            flow += f;

            a -= f;

            if(a == 0) break;

        }

    }

    return flow;

}

int maxflow(){

   int flow = 0;

   while(BFS()){

       memset(cur,0,sizeof(cur));

       flow += DFS(src,INF);

   }

   return flow;

}

int main()

{

   // freopen("Input.txt","r",stdin);

    int T;

    scanf("%d",&T);

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

        scanf("%d%d",&N,&M);

        init();

        int sum = 0,x;

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

            scanf("%d",&x);

            addEdge(ss,i,x - sum);

            sum = x;

        }

        sum = 0;

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

            scanf("%d",&x);

            addEdge(i+N,tt,x - sum);

            sum = x;

        }

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

            for(int j = 1;j <= M;++j){

              addEdge(i,sink,1);

              addEdge(i,N + j,19);

              addEdge(src,N + j,1);

            }

        }

        addEdge(tt,ss,INF);

       int flow = maxflow();

        src = ss; sink = tt;

        maxflow();

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

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

            for(int j = 0;j < (int)G[i].size();++j){

                Edge& e = edges[G[i][j]];

                if(e.from > N||e.to <= N||e.to > N+M) continue;

                ans[e.from][e.to - N] = e.flow + 1;

            }

        }

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

            for(int j = 1;j <= M;++j)

                printf("%d%c",ans[i][j],j == M ? '\n':' ');

        }

    }

    return 0;

}