dinicT飞求助
查看原帖
dinicT飞求助
408071
TankYu楼主2023/7/13 18:35
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cassert>
#define D double
#define LD long double
#define LL long long
#define ULL unsigned long long
#define S string
#define fi first
#define se second
#define mp make_pair
#define int LL
using namespace std;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
const int N = 2E6 + 100;
#define getchar() (p1 == p2 &&(p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)

inline int rd()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
		x = x * 10 + (ch ^ 48), ch = getchar();
	return x * f;
}

int n, m, s, t;
int cur[500010];
struct edge
{
	int v;
	LL w;
	int nxt;
} e[4000010];
int head[500010];
int col[500010];
int maxcnt = -1;

void add(int u, int v, LL w)
{
	maxcnt++;
	e[maxcnt] = {v, w, head[u]};
	head[u] = maxcnt;
}

void addd(int u, int v, int w)
{
	add(u, v, w);
	add(v, u, 0);
}

LL dfs(int now, LL flow)
{
	if (now == t)
	{
		return flow;
	}
	int rest = flow;
	for (int &i = cur[now]; i != -1; i = e[i].nxt)
	{
		if (rest == 0)
		{
			return flow;
		}
		if (col[e[i].v] == col[now] + 1 && e[i].w != 0)
		{
			int flow_ = dfs(e[i].v, min(flow, e[i].w));
			if (flow_ > 0)
			{
				rest -= flow_;
				e[i].w -= flow_;
				e[i ^ 1].w += flow_;
				return flow_;
			}
		}
	}
	return 0;
}

bool bfs()
{
	queue<int> q;
	while (!q.empty())
		q.pop();
	for (int i = 0; i <= n + 2 * m + 1; i++)
	{
		col[i] = 0;
	}
	col[s] = 1;
	q.push(s);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = head[x]; i != -1; i = e[i].nxt)
		{
			if (e[i].w > 0 && !col[e[i].v])
			{
				col[e[i].v] = col[x] + 1;
				q.push(e[i].v);
				if (e[i].v == t)
				{
					return true;
				}
			}
		}
	}
	if (col[t])
	{
		return true;
	}
	return false;
}

LL max_flow()
{
	LL ans = 0;
	while (bfs())
	{
		while (true)
		{
			for (int i = 0; i <= n + 2 * m + 1; i++)
			{
				cur[i] = head[i];
			}
			LL flow = dfs(s, 0x3f3f3f3f3f3f);
			if (flow == 0)
			{
				break;
			}
//			cout << flow << '\n';
			ans += flow;
		}

	}
	return ans;
}

int a[100010], b[100010];

signed main()
{
//	freopen("P1361_3.in", "r", stdin);
	n = rd();
	LL ans = 0;
	for (int i = 1; i <= n; i++)
	{
		a[i] = rd();
		ans += a[i];
	}
	for (int i = 1; i <= n; i++)
	{
		b[i] = rd();
		ans += b[i];
	}
	m = rd();
	memset(head, -1, sizeof(head));
	s = 0;
	t = n + 2 * m + 1;
	for (int i = 1; i <= n; i++)
	{
		addd(s, i, a[i]);
		addd(i, t, b[i]);
	}
	for (int i = 1; i <= m; i++)
	{
		int k, c1, c2;
		k = rd();
		c1 = rd();
		c2 = rd();
		ans += c1;
		ans += c2;
		addd(0, n + i, c1);
		addd(n + m + i, t, c2);
		for (int j = 1; j <= k; j++)
		{
			int x;
			x = rd();
			addd(n + i, x, 0x3f3f3f3f3f3f);
			addd(x, n + m + i, 0x3f3f3f3f3f3f);
		}
	}
//	cout << 1;
	cout << ans - max_flow();
	return 0;
}
2023/7/13 18:35
加载中...