gym 101170 NWERC 2016 J Jupiter Orbiter

Problem

Northwestern European Regional Contest 2016
vjudge.net/problem/Gym-101170J

Meaning

有 s 个传感器（产生数据）、q 个 FIFO 式的队列（放数据），每个队列有个容量 $q_{i}$。
每个传感器都会绑定一个队列，即只把数据放到那。
每次传感器想把数据放进队列，当且仅当它绑定的队列剩余的容量足够将它产生的所有数据全部放进去，否则数据丢失。
有 n 个回合，每次每个传感器产生 $s_{i}$ 的数据，而此次能传回地球的总数据量是 d，问 n 个回合后能不能把所有数据都传回地球。

Analysis

每个回合都是先产生数据，然后进行传数据回地球的操作。
放数据要一次全部放，但取数据可以将同一次的数据拆开几次传，或几次的数据放到同一次传。
所以每个回合就扫一遍 s 个传感器产生的数据，先考虑塞进队列，如果塞爆了，就（从队头）取出一部分（超出多少取多少）“溢出数据”在这个回合传回地球，否则先留在队列里。
由于一次回传的空间不能累积到下一次（过了就没），所以如果此次的回传总量减掉上面那些溢出的数据后，还有剩余可用，要尽量用上：如果能把所有队列的所有数据全部传完，就全部传完；但如果只能传一部份，就要考虑传那些队列的数据？一条队列传多少？
这样很难判断，不如将判断留到下次，将剩余容量累积到下次（其实并不是真的“累积”到下次，而是在这次用了，只是下次再一起算）。
（还有最大流的写法，按队友的说法：最大流是智能的贪心…见下面链接）

Max-Flow Version

Codeforces Gym101170J：Jupiter Orbiter（最大流）

Code

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 30, Q = 30, S = 100;

int sq[S]; // mapping from Sensor to Queue
int c[Q+1]; // Capacity of queue-i
int dt[Q+1]; // data loaded in queue-i

bool solve(int n, int q, int s)
{
    memset(dt, 0, sizeof dt);
    int cap = 0; // 回传容量
    for(int d, rest; n--; )
    {
        scanf("%d", &d);
        for(int i = 0, a, qid; i < s; ++i)
        {
            scanf("%d", &a);
            qid = sq[i];
            if(a > c[qid]) // 单次数据整个队列都装不下
                return false;
            dt[qid] += a; // 将数据塞进队列
            if(dt[qid] > c[qid]) // 塞爆了
            {
                cap -= dt[qid] - c[qid]; // 从队头取溢出部分
                if(cap < 0) // 溢出的总数据太多，不够装
                    return false;
                dt[qid] = c[qid];
            }
        }
        cap += d; // 这句话在这，因为先产生数据，再传回地球
        rest = 0;
        for(int i = 1; i <= q; ++i)
            rest += dt[i];
        if(rest <= cap)
        {
            cap = 0;
            for(int i = 1; i <= q; ++i)
                dt[i] = 0;
        }
    }
    // 最后一次回传，必须全部带走
    for(int i = 1; i <= q; ++i)
        cap -= dt[i];
    return cap >= 0;
}

int main()
{
    int n, q, s;
    scanf("%d%d%d", &n, &q, &s);
    for(int i = 0; i < s; ++i)
        scanf("%d", sq+i);
    for(int i = 1; i <= q; ++i)
        scanf("%d", c+i);
    puts(solve(n, q, s) ? "possible" : "impossible");
    return 0;
}