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 = http://www.mamicode.com/tt + 1; sink = src + 1;>

 
uva Matrix Decompressing (行列模型)