某岛

… : "…アッカリ~ン . .. . " .. .
August 19, 2010

ZOJ 1994. Budget

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