BZOJ4334【JSOI2012】铁拳 <上下界网络流>

Posted on Symbols count in article: 2.1k Reading time ≈ 8 mins.

Problem

【JSOI2012】铁拳

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  256  MB\mathrm{Memory\;Limit:\;256\;MB}

Description

经过了可怕的第三次世界大战后，国家政府崩溃，各大财团趁机夺取掌控世界。长年战争后，八大财团幸存并割据一方，其中最强的当属掌控北美的铁拳。
在铁拳财团所维护的文明区域中，有一项最为光荣、重要的赛事——Iron  Fist\mathrm{Iron\;Fist}，也就是铁拳大赛。IF\mathrm{IF}中云集了世界各地各财团鼎力资助的世外高手，只为了赢得IF  Champion\mathrm{IF\;Champion}，得到无上的荣耀，当然还有随之而来的权力。本来一切秩序井然，但一个来自贫民窟的少年风间仁意外地在海选中赢了IF\mathrm{IF}正式选手，获得了决赛资格，从此格局被打乱……
为了应对这突如其来的变数，IF\mathrm{IF}管理层决定先对联盟中所有的选手进行评估，以更好地掌握大局。
知最近mm届比赛出现过的nn位选手，背后都有着各自财团的资助，并且签下了合同。由于这是各财团的高度机密，合同的具体细节无从得知，但铁拳财团的间谍们通过各种渠道得知了每个选手的薪金范围（显然薪金是非负数）。
对于最近mm届的IF\mathrm{IF}比赛（从11开始编号），每一届联盟都会进行清算，通过国际金融手段准确计算出这一届联盟选手身价总和的变化。每一届中，会有一些新选手加入，也会有部分选手在比赛中丧失了战斗能力，而被踢出联盟，流放到贫民窟。
现在给出联盟中nn位选手的身价范围，以及他们 进入联盟的届数（00表示在m+1m+1届以前就已经是联盟选手） 和 离开联盟的届数（00表示是现役选手）。同时给出最近mm届中，每一届联盟选手身价总和减去上一届的值。
请你根据现有信息，尽可能准确地给出每个选手可能的薪金范围。各选手之间的薪金范围可以不同时成立，但对于一位选手的范围中的每一个数，都必须至少存在一种合法方案使该选手能得到相应薪金，而且这个范围跨度要尽可能大。
如果输入信息有误，请输出−1-1，表示无解。

Input

第一行一个正整数mm，意义见上（下同）。
第二行包含mm个整数，第ii个表示第ii届中 选手身价总和 的变化情况。
第三行一个正整数nn。
接下来n行，每行包含四个整数，分别表示 身价下限 、 身价上限 、 出道届数 、 退役届数，细节请参照上文。
保证出道时间严格比退役时间小（00除外）。

Output

一行，输出最小的答案。

Sample Input

1
2
3
4
5
6
2
5 -1
3
1 4 1 0
2 3 1 0
1 5 1 2

Sample Output

1
2
3
1.00 2.00
2.00 3.00
1.00 1.00

HINT

样例解释
第二届只有33号离开了，可以锁定33号的薪金是11。
如此一来，11号和22号薪金之和为44，那么11号最少能拿11，最多能拿22；22号最少能拿到22，最多能拿到33。
数据规模
对于100%100\%的数据，n≤200n\le 200，m≤100m\le 100，给定薪金范围不超过2000020000。
应上传者要求，此题不公开，如有异议，请提出.

标签：线性规划 上下界网络流

Solution

线性规划转上下界网络流。
挺麻烦的。

首先这些条件可以看作mm个等式，故可转化为线性规划。而解线性规划只有网络流和单纯形两种，不会单纯形，所以用了网络流。

将每个等式作为一个点，每个变量作为一条边，不难发现一个变量只会进入等式一次，出等式一次。若此变量从ll等式进，从rr等式出，范围为[lo,hi][lo, hi]，则连边l→rl\to r，容量为[lo,hi][lo,hi]。对于l=0l=0的变量，则连边s→rs\to r；对于r=0r=0的变量，则连边l→tl\to t。
接下来处理每个等式的差值。可以发现等式i−1i-1与ii的差值可以用边s→is\to i或i→ti\to t表示，即为从源点补进来多少流量或从汇点分出去多少流量。因而可以连边：设等式i−1i-1与ii的差值为gapigap_i，若gapi>0gap_i>0，则连边S→iS\to i，容量为gapigap_i；若gapi<0gap_i<0，则连边i→Ti\to T，容量为−gapi-gap_i。
这样就可以构建出一个上下界网络流的模型。

建模后，可以在一开始就跑一遍可行流，判断是否有解。

之后有两种做法：

法11：对每条边的取值进行二分，分别去找最大值和最小值，每次checkcheck的时候把重设当前边的范围，跑可行流验证。

法22：对于每条边，找到先前求可行流时它的流量，考虑它最多可以再少承担多少流量或多承担多少流量。那么可以在残量网络上断掉当前边，以起点为源，终点为汇，跑最大流得到它最多可以减少多少流量；再以终点为汇，起点为源，跑最大流得到它最多可以增加多少流量。设最多可以减少maxDecreasemaxDecrease，最多可以增加maxIncreasemaxIncrease，此边的下限为lolo，上限为hihi，可行流中此边的流量为curcur，则答案为lo+cur−maxDecreaselo+cur-maxDecrease和lo+cur+maxIncreaselo+cur+maxIncrease。这里需要注意两个答案都需要在[lo,hi][lo,hi]之间，即最终答案应该为max(lo,lo+cur−maxDecrease)max(lo,lo+cur-maxDecrease)和min(hi,lo+cur+maxIncrease)min(hi,lo+cur+maxIncrease)。

建议使用法22，同时%%%巨佬Joker\%\%\%巨佬Joker提供优质法22。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define MAX_N 1000
#define MAX_M 2000
#define INF 0x7f7f7f7f
using namespace std;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct node {int v, c, nxt;} E[MAX_M+5], cpy[MAX_M+5];
int n, m, s, t, ss, tt, cnt, d[MAX_N+5], pr[MAX_N+5], mat[MAX_N+5];
int gap[MAX_N+5], range[MAX_N+5][2], zone[MAX_N+5][2];    bool mrk[MAX_N+5];
void init() {ss = m+1, tt = m+2, s = 0, t = m+3, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
int addedge(int u, int v, int c) {return insert(u, v, c), insert(v, u, 0), cnt-2;}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c || mrk[i]) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow;	int ret = 0;
    for (int i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c || mrk[i]) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
int Dinic() {int ret = 0;    while (BFS()) ret += DFS(s, INF);	return ret;}
bool get_ava() {
    int into = 0, outo = 0;
    init(), memset(d, 0, sizeof d);	addedge(tt, ss, INF);
    for (int i = 1; i <= m; i++) {
        if (gap[i] > 0) d[ss] += gap[i], d[i] -= gap[i];
        if (gap[i] < 0) d[i] -= gap[i], d[tt] += gap[i];
    }
    for (int i = 1; i <= n; i++) {
        int u = zone[i][0] == 0 ? ss : zone[i][0];
        int v = zone[i][1] == 0 ? tt : zone[i][1];
        mat[i] = addedge(u, v, range[i][1]-range[i][0]);
        d[u] += range[i][0], d[v] -= range[i][0];
    }
    for (int i = s+1; i <= t-1; i++) {
        if (d[i] < 0) addedge(s, i, -d[i]), into -= d[i];
        if (d[i] > 0) addedge(i, t, d[i]), outo += d[i];
    }
    return into == outo && Dinic() == into;
}
void rec() {for (int i = 0; i < cnt; i++) E[i] = cpy[i];}
int main() {
    read(m);	for (int i = 1; i <= m; i++) read(gap[i]);
    read(n);	for (int i = 1; i <= n; i++) read(range[i][0]), read(range[i][1]), read(zone[i][0]), read(zone[i][1]);
    if (!get_ava()) {puts("-1"); return 0;}	for (int i = 0; i < cnt; i++) cpy[i] = E[i];
    for (int i = 1; i <= n; i++) {
        int eid = mat[i], base = E[eid^1].c, ori = E[eid].c+base;	mrk[eid] = mrk[eid^1] = true;
        s = E[eid^1].v, t = E[eid].v, printf("%d.00 ", range[i][0]+max(base-Dinic(), 0)), rec();
        s = E[eid].v, t = E[eid^1].v, printf("%d.00\n", range[i][0]+min(base+Dinic(), ori)), rec();
        mrk[eid] = mrk[eid^1] = false;
    }
    return 0;
}