Участник:Easik/SHOP2

Материал из DISCOPAL
Перейти к: навигация, поиск

C \ gcc

#include <stdio.h>
#include <stdlib.h>  /* rand(), srand() */
#include <string.h>  /* strlen() */
#include <assert.h>  /* assert() */
#include <stdbool.h> /* bool */
#include <time.h>    /* time() */
 
#define QUEUE_SIZE 10000
 
#define MAX_VERTICES 5000
#define INF (int)1e9
 
typedef struct {
 
	int u, v;
    int cap, next;
 
} edge;
 
int V, E;
int N, M;
int sum, ans;
int src, snk;
 
edge edges[1 << 19];
int flow[MAX_VERTICES];
int from[MAX_VERTICES];
int first[MAX_VERTICES];
int nc[MAX_VERTICES];
int mc[MAX_VERTICES];
 
 
void reflow();
bool augment(int src, int snk);
void add_edge(int u, int v, int cap);
 
 
int main() {
 
    int i;
    int u, v;
    int T;
    int cant;
 
	scanf("%d", &T);
	while (T--) {
 
        scanf("%d %d", &N, &M);
 
		src = N + M;
		snk = N + M + 1;
 
		V = N + M + 2;
 
		ans = 0;
        sum = 0;
		E = 0;
 
        for (i = 0; i <= V; i++) first[i] = -1;
 
        for (i = 0; i < N; i++) {
 
            scanf("%d", &nc[i]);
 
			add_edge(src, i, nc[i]);
			sum += nc[i];
 
        }
 
        for (i = 0; i < M; i++) {
 
            scanf("%d", &mc[i]);
 
            add_edge(i + N, snk, mc[i]);
 
        }
 
        for (i = 0; i < M; i++) {
 
            scanf("%d", &cant);
			while (cant--) {
 
				scanf("%d", &u);
				u--;
 
				add_edge(u, N + i, INF);
 
				flow[snk] = (mc[i] <= nc[u]) ? mc[i] : nc[u];
 
                if (flow[snk]) {
 
                    nc[u] -= flow[snk];
					mc[i] -= flow[snk];
 
					from[snk] = 2 * N + 2 * i;
    				from[N + i] = E - 2;
 
					from[u] = 2 * u;
					from[src] = -1;
 
					reflow();
 
				}
 
			}
 
        }
 
		while (augment(src, snk));
 
		printf("%d\n", sum - ans);
 
	}
 
	return 0;
 
}
 
void reflow() {
 
    int i;
 
    for (i = from[snk]; i != -1; i = from[edges[i].u]) {
 
		edges[i].cap -= flow[snk];
 		edges[i^1].cap += flow[snk];
 
	}
 
	ans += flow[snk];
 
}
 
 
bool augment(int src, int snk) {
 
    int i;
    int u, v;
    int queue[QUEUE_SIZE];  /* Won't shift all items when dequeue happens */
    int queue_front = 0, queue_back = 0;
 
    for (i = 0; i <= V; i++) flow[i] = 0;
    flow[src] = INF;
    from[src] = -1;
 
    queue[queue_back++] = src;
    while (queue_back - queue_front > 0) {
 
        u = queue[queue_front];
 
        for (i = first[u]; i != -1; i = edges[i].next) {
 
            v = edges[i].v;
 
            if (!edges[i].cap) {
 
                continue;
 
            }
 
            if (flow[v]) {
 
                continue;
 
            }
 
            flow[v] = (edges[i].cap <= flow[u]) ? edges[i].cap : flow[u];
            from[v] = i;
            /* assert(queue_back < QUEUE_SIZE); */
            queue[queue_back++] = v;
 
        }
 
        if (flow[snk]) {
 
            break;
 
        }
 
        queue_front++;
 
    }
 
    if (!flow[snk]) {
 
        return 0;
 
    }
 
	reflow();
 
	return 1;
 
}
 
 
void add_edge(int u, int v, int cap) {
 
    /* Set direct edge */
	edges[E] = (edge){u, v, cap, first[u]};
	first[u] = E++;
 
    /* Set inverse edge */
	edges[E] = (edge){v, u, 0, first[v]};
	first[v] = E++;
 
}