Codeforces Gym101170J：Jupiter Orbiter（最大流）

题目链接

题意

有n次事件，q个队列，s个传感器。每个传感器接到一个队列，每个队列有一个容量。

接下来执行n次事件，每次事件都会有一个最大发送数据量d。和s个数据a，代表这次给每个s填入a的数据量。

每次事件执行完后都要将队列里面的数据发送总和为d的数据量。这一次事件的数据发送后队列剩余的数据可以给下一次事件用。问是否会有数据泄露（即给s填入的数据量能不能都发送出去）。

思路

最大流。

建图如下：

S->第i个事件的队列q1->第i个事件的队列q2->事件->T

第i个事件的队列q2->第i+1个事件的队列q1

容量：

S->第i个事件的所有队列q1 的容量为b，即输入给队列的数据量。

第i个事件的队列q1->第i个事件的队列q2->事件 和

第i个事件的队列q2->第i+1个事件的队列q1 的容量为c，即每个队列的最大容量。

事件->T 的容量为d，即每次可以放出去的数据量。

判断是否合法：∑b <= 最大流量。

#include <bits/stdc++.h>

using namespace std;

const int N = 2150;

const int INF = 0x3f3f3f3f;

typedef long long LL;

struct Edge {

	int u, v, nxt, cap;

} edge[N*N*2];

int head[N], tot, cur[N], gap[N], dis[N], pre[N], qq[N], cc[N];

void Add(int u, int v, int cap) {

	edge[tot] = (Edge) { u, v, head[u], cap }; head[u] = tot++;

	edge[tot] = (Edge) { v, u, head[v], 0 }; head[v] = tot++;

}

int BFS(int S, int T) {

    queue<int> que; que.push(T);

    memset(dis, INF, sizeof(dis));

    memset(gap, 0, sizeof(gap));

    gap[0]++; dis[T] = 0;

    while(!que.empty()) {

        int u = que.front(); que.pop();

        for(int i = head[u]; ~i; i = edge[i].nxt) {

            int v = edge[i].v;

            if(dis[v] == INF) {

                dis[v] = dis[u] + 1;

                gap[dis[v]]++;

                que.push(v);

            }

        }

    }

}

int ISAP(int S, int T, int n) {

    BFS(S, T);

    memcpy(cur, head, sizeof(cur));

    int u = pre[S] = S, i, index, flow, ans = 0;

    while(dis[S] < n) {

        if(u == T) {

            flow = INF, index = S;

            for(i = S; i != T; i = edge[cur[i]].v)

                if(flow > edge[cur[i]].cap) flow = edge[cur[i]].cap, index = i;

            for(i = S; i != T; i = edge[cur[i]].v)

                edge[cur[i]].cap -= flow, edge[cur[i]^1].cap += flow;

            ans += flow, u = index;

        }

        for(i = cur[u]; ~i; i = edge[i].nxt)

            if(edge[i].cap > 0 && dis[edge[i].v] == dis[u] - 1) break;

        if(~i) {

            pre[edge[i].v] = u; cur[u] = i; u = edge[i].v;

        } else {

            if(--gap[dis[u]] == 0) break;

            int md = n;

            for(i = head[u]; ~i; i = edge[i].nxt)

                if(md > dis[edge[i].v] && edge[i].cap > 0) md = dis[edge[i].v], cur[u] = i;

            gap[dis[u] = md + 1]++;

            u = pre[u];

        }

    }

    return ans;

}

int main() {

	int n, q, s; scanf("%d%d%d", &n, &q, &s);

	memset(head, -1, sizeof(head)); tot = 0;

	int S = 0, T = n * q * 2 + n + 1;

	for(int i = 1; i <= s; i++) scanf("%d", &qq[i]);

	for(int i = 1; i <= q; i++) scanf("%d", &cc[i]);

	int sum = 0;

	for(int i = 1; i <= n; i++) {

		int d; scanf("%d", &d);

		Add(n * q * 2 + i, T, d); // 事件与汇点

		for(int j = 1; j <= s; j++) {

			int a; scanf("%d", &a); sum += a;

			Add(S, qq[j] + (i - 1) * q, a); // 源点与第一个队

		}

		for(int j = 1; j <= q; j++) {

			Add((i - 1) * q + j, (i - 1) * q + j + n * q, cc[j]); // 第一个队和第二个队

			Add((i - 1) * q + j + n * q, n * q * 2 + i, cc[j]); // 第二个队和事件

			if(i < n) Add((i - 1) * q + j + n * q, i * q + j, cc[j]); // 第二个队和下一个事件的第一个队

		}

	}

//	int ans = ISAP(S, T, T + 1);

//	printf("ans : %d\n", ans);

	if(sum <= ISAP(S, T, T + 1)) puts("possible");

	else puts("impossible");

	return 0;

}