Brief description :

给定一个矩阵的各种限制，问是否存在可行解。

Analyse :

… 连边构图，转化成有上下界的流网络是否存在可行流的问题。

/*
    Author: xiaodao
    Prob: ZOJ 1994. / POJ 2396. Budget
    Status: Accepted
    Tags: Network-Flow, Dinitz
    Last modify: GMT +8 Aug.19th 08:13
*/

#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x7fffffff;
const int ROW = 201, COL = 21;
const int N = ROW*COL+ROW+COL+4, M = 4000000;


struct edge{
    int v, c;
    void insert(int, int);
};

struct node{
    vector adj;
    int D;
};

struct network_flow{
    node V[N+1]; edge E[M+1];
    int edge_count, max_flow, necessary_flow;
    int n, m, s, t;
    void init();
    void add_edge(int, int, int);
    void add_edge(int, int, int, int);
    void bfs();
    void Dinitz();
};

int _r(int x){
    return x ^ 1;
}


void edge::insert(int a, int b){
    v = a; c = b;
};

void network_flow::add_edge(int x, int y, int c){
    V[x].adj.push_back(edge_count); E[edge_count++].insert(y, c);
    V[y].adj.push_back(edge_count); E[edge_count++].insert(x, 0);
}

void network_flow::add_edge(int x, int y, int l, int r){
    add_edge(x, y, r-l); add_edge(s, y, l); add_edge(x, t, l);
    necessary_flow += l;
}

void network_flow::bfs(){
    int Q[N], head, tail;
    for (int i=1;i<=n;i++) V[i].D = -1; //memset(V.D, -1, sizeof(V.D));
    head = 0; tail = 1; Q[0] = s; V[s].D = 0;

    int u;
    while (headR[i][j]) return true;
    return false;
}




void load(network_flow &G){
    G.init(); sum_row = sum_column = 0;

    int s, t;
    scanf("%d%d", &r, &c);
    s = r * c + r + c + 1; t = s + 1;
    G.s = 0; G.n = G.t = t + 1;



    int cc;
    for (int i=1;i<=r;i++){
        scanf("%d", &cc);
        G.add_edge(s, row(i), cc, cc);
        sum_row += cc;
    }

    for (int i=1;i<=c;i++){
        scanf("%d", &cc); G.add_edge(column(i), t, cc, cc);
        sum_column += cc;
    }

    for (int i=1;i<=r;i++)
        for (int j=1;j<=c;j++)
            L[i][j] = 0, R[i][j] = INF;

    int a, b; char ccc; int d;
    int a0, b0, ar, bc;

    scanf("%d", &cc);
    for (int i=0;i') L[a][b] = max(L[a][b], d+1);
                else if (ccc=='<') R[a][b] = min(R[a][b], d-1);
                else L[a][b] = max(L[a][b], d), R[a][b] = min(R[a][b], d);
            }
    }

    for (int i=1;i<=r;i++)
        for (int j=1;j<=c;j++){
            G.add_edge(row(i), (i-1)*c+j, L[i][j], R[i][j]);
            h1[i][j] = &G.E[G.edge_count-3].c;
            h2[i][j] = &G.E[G.edge_count-5].c;
        }


    for (int i=0;iR[i][j]) return false;
    return true;
}



int main(){
    //freopen("budget.in", "r", stdin);
    //freopen("budget.out", "w", stdout);
    int T; cin >> T;
    for (int i=0;i
Further discussion :
我是照着一份题单往下做的，因此还没读题就开始网络流了，（但是这题居然把自己包裹成一个矩阵。。其实要是数据规模稍微再给我一点的话，我就要想着搜索剪枝了。。）一次性编写那么长的代码，还是蛮令我头痛的，好在硬着头皮写下来了...
在我写这题之前，包括现在，我一直认为可以给这题开发一个特制算法，因为每行和不是固定的么。（而且注意到呀，行列不一样多呢。#）。。可以像 Relabel_to_Front 里那样维护一个前置流（preflow），然后 ....（并且这个网络的深度很浅，应该这些都是可以再想想的地方，不过我还是先写一个比较格式化的先A了他再说，至于接下来我想还有一些工作...）
1. 此题是一个稀疏图，因此不可以用邻接矩阵，但这样就会带来很多问题，比如说不能像之前那样简单的处理反向边。（不过这几天准备网络流，我也积累了一些不同的经验，各方面的都有一些，再做几道练习之后我会写个小结。）
2. 对于条件的处理，我开了 L, R 两个数组，感觉代码还是很整齐的。（啊，this-> 指针可以省略呀。。）写成这样以后，大概整个效率会慢 4 个常数倍，不过考虑到现在并不是特别追求速度，所以就当看不见了，边目录先是单独放在一个独立的数组里的，然后邻接表里在单独存索引。（这样的一个好处是，可以用一步标准的异或运算获得反向边。）（关于这点，请参考代码的第 216 至 217 行。。。0(∩_∩)o ）
3. 我在开始网络流之前做了一些必要性判断，比如说如果不这么做的话，有可能求出负数呀。还有一些问题有人质疑这题的 Special_judge ，于是我自己写了个检测的子程序。（不过这题WA的原因也许是你行尾留有多余的一个空格或者最后多打印一个空格。类似的情况在两个 OJ 里都不会报 PE 了，要特别小心才是，例如这一题，如果我把最后输出空行的那个语句换成不加最后一个判断的，那么在 POJ 上仍然可以 AC，但 ZOJ 就 WA 了，这样的原因非常浪费时间，（特别是我们总要看到 AC 以后感觉一块石头落了地）因此在最后一条特别指出。）
External link :
http://acm.pku.edu.cn/JudgeOnline/problem?id=2396

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=994

http://hi.baidu.com/forsona/blog/item/662c07d5401fd209a18bb709.html
                                                												

													Posted by 
													xiaodao													
													Category: 													日常