Dinic #网络流 #拓扑排序

每个点向保护的点建图，对这个图拓扑排序，然后就是求这个图的最大完全子图，就是 \(dinic\) 板子

// Author: xiaruize
#ifndef ONLINE_JUDGE
bool start_of_memory_use;
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
namespace __DEBUG_UTIL__
{
	using namespace std;
	/* Primitive Datatypes Print */
	void print(const char *x) { cerr << x; }
	void print(bool x) { cerr << (x ? "T" : "F"); }
	void print(char x) { cerr << '\'' << x << '\''; }
	void print(signed short int x) { cerr << x; }
	void print(unsigned short int x) { cerr << x; }
	void print(signed int x) { cerr << x; }
	void print(unsigned int x) { cerr << x; }
	void print(signed long int x) { cerr << x; }
	void print(unsigned long int x) { cerr << x; }
	void print(signed long long int x) { cerr << x; }
	void print(unsigned long long int x) { cerr << x; }
	void print(float x) { cerr << x; }
	void print(double x) { cerr << x; }
	void print(long double x) { cerr << x; }
	void print(string x) { cerr << '\"' << x << '\"'; }
	template <size_t N>
	void print(bitset<N> x) { cerr << x; }
	void print(vector<bool> v)
	{ /* Overloaded this because stl optimizes vector<bool> by using
		  _Bit_reference instead of bool to conserve space. */
		int f = 0;
		cerr << '{';
		for (auto &&i : v)
			cerr << (f++ ? "," : "") << (i ? "T" : "F");
		cerr << "}";
	}
	/* Templates Declarations to support nested datatypes */
	template <typename T>
	void print(T &&x);
	template <typename T>
	void print(vector<vector<T>> mat);
	template <typename T, size_t N, size_t M>
	void print(T (&mat)[N][M]);
	template <typename F, typename S>
	void print(pair<F, S> x);
	template <typename T, size_t N>
	struct Tuple;
	template <typename T>
	struct Tuple<T, 1>;
	template <typename... Args>
	void print(tuple<Args...> t);
	template <typename... T>
	void print(priority_queue<T...> pq);
	template <typename T>
	void print(stack<T> st);
	template <typename T>
	void print(queue<T> q);
	/* Template Datatypes Definitions */
	template <typename T>
	void print(T &&x)
	{
		/*  This works for every container that supports range-based loop
			i.e. vector, set, map, oset, omap, dequeue */
		int f = 0;
		cerr << '{';
		for (auto &&i : x)
			cerr << (f++ ? "," : ""), print(i);
		cerr << "}";
	}
	template <typename T>
	void print(vector<vector<T>> mat)
	{
		int f = 0;
		cerr << "\n~~~~~\n";
		for (auto &&i : mat)
		{
			cerr << setw(2) << left << f++, print(i), cerr << "\n";
		}
		cerr << "~~~~~\n";
	}
	template <typename T, size_t N, size_t M>
	void print(T (&mat)[N][M])
	{
		int f = 0;
		cerr << "\n~~~~~\n";
		for (auto &&i : mat)
		{
			cerr << setw(2) << left << f++, print(i), cerr << "\n";
		}
		cerr << "~~~~~\n";
	}
	template <typename F, typename S>
	void print(pair<F, S> x)
	{
		cerr << '(';
		print(x.first);
		cerr << ',';
		print(x.second);
		cerr << ')';
	}
	template <typename T, size_t N>
	struct Tuple
	{
		static void printTuple(T t)
		{
			Tuple<T, N - 1>::printTuple(t);
			cerr << ",", print(get<N - 1>(t));
		}
	};
	template <typename T>
	struct Tuple<T, 1>
	{
		static void printTuple(T t) { print(get<0>(t)); }
	};
	template <typename... Args>
	void print(tuple<Args...> t)
	{
		cerr << "(";
		Tuple<decltype(t), sizeof...(Args)>::printTuple(t);
		cerr << ")";
	}
	template <typename... T>
	void print(priority_queue<T...> pq)
	{
		int f = 0;
		cerr << '{';
		while (!pq.empty())
			cerr << (f++ ? "," : ""), print(pq.top()), pq.pop();
		cerr << "}";
	}
	template <typename T>
	void print(stack<T> st)
	{
		int f = 0;
		cerr << '{';
		while (!st.empty())
			cerr << (f++ ? "," : ""), print(st.top()), st.pop();
		cerr << "}";
	}
	template <typename T>
	void print(queue<T> q)
	{
		int f = 0;
		cerr << '{';
		while (!q.empty())
			cerr << (f++ ? "," : ""), print(q.front()), q.pop();
		cerr << "}";
	}
	/* Printer functions */
	void printer(const char *) {} /* Base Recursive */
	template <typename T, typename... V>
	void printer(const char *names, T &&head, V &&...tail)
	{
		/* Using && to capture both lvalues and rvalues */
		int i = 0;
		for (size_t bracket = 0; names[i] != '\0' and (names[i] != ',' or bracket != 0); i++)
			if (names[i] == '(' or names[i] == '<' or names[i] == '{')
				bracket++;
			else if (names[i] == ')' or names[i] == '>' or names[i] == '}')
				bracket--;
		cerr.write(names, i) << " = ";
		print(head);
		if (sizeof...(tail))
			cerr << " ||", printer(names + i + 1, tail...);
		else
			cerr << "]\n";
	}
	/* PrinterArr */
	void printerArr(const char *) {} /* Base Recursive */
	template <typename T, typename... V>
	void printerArr(const char *names, T arr[], size_t N, V... tail)
	{
		size_t ind = 0;
		for (; names[ind] and names[ind] != ','; ind++)
			cerr << names[ind];
		for (ind++; names[ind] and names[ind] != ','; ind++)
			;
		cerr << " = {";
		for (size_t i = 0; i < N; i++)
			cerr << (i ? "," : ""), print(arr[i]);
		cerr << "}";
		if (sizeof...(tail))
			cerr << " ||", printerArr(names + ind + 1, tail...);
		else
			cerr << "]\n";
	}
}
#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << __LINE__ << ": [", __DEBUG_UTIL__::printer(#__VA_ARGS__, __VA_ARGS__)
#define debugArr(...) std::cerr << __LINE__ << ": [", __DEBUG_UTIL__::printerArr(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...)
#define debugArr(...)
#endif
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
	if (a > b)
		return a;
	return b;
}
int min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e6 + 10;

struct MF
{
	struct edge
	{
		int v, nxt, cap, flow;
	} e[N];

	int fir[N], cnt = 0;

	int n, S, T;
	int maxflow = 0;
	int dep[N], cur[N];

	void init()
	{
		// cerr << "flag" << endl;
		memset(fir, -1, sizeof(fir));
		cnt = 0;
	}

	void addedge(int u, int v, int w)
	{
		e[cnt] = {v, fir[u], w, 0};
		fir[u] = cnt++;
		e[cnt] = {u, fir[v], 0, 0};
		fir[v] = cnt++;
	}

	bool bfs()
	{
		queue<int> q;
		memset(dep, 0, sizeof(int) * (n + 1));

		dep[S] = 1;
		q.push(S);
		while (q.size())
		{
			int u = q.front();
			q.pop();
			for (int i = fir[u]; ~i; i = e[i].nxt)
			{
				int v = e[i].v;
				if ((!dep[v]) && (e[i].cap > e[i].flow))
				{
					dep[v] = dep[u] + 1;
					q.push(v);
				}
			}
		}
		return dep[T];
	}

	int dfs(int u, int flow)
	{
		if ((u == T) || (!flow))
			return flow;

		int ret = 0;
		for (int &i = cur[u]; ~i; i = e[i].nxt)
		{
			int v = e[i].v, d;
			if ((dep[v] == dep[u] + 1) && (d = dfs(v, min(flow - ret, e[i].cap - e[i].flow))))
			{
				ret += d;
				e[i].flow += d;
				e[i ^ 1].flow -= d;
				if (ret == flow)
					return ret;
			}
		}
		return ret;
	}

	void dinic()
	{
		while (bfs())
		{
			memcpy(cur, fir, sizeof(int) * (n + 1));
			maxflow += dfs(S, INF);
			// cerr << maxflow << endl;
		}
	}
} mf;

int n, m;
int s[N];
vector<int> g[N];
int deg[N];
int d[N], t[N];

int id(int x, int y)
{
	return (x - 1) * m + y;
}

void solve()
{
	cin >> n >> m;
	rep(i, 1, n)
	{
		rep(j, 1, m)
		{
			cin >> s[id(i, j)];
			if (j > 1)
			{
				g[id(i, j)].push_back(id(i, j - 1));
				deg[id(i, j - 1)]++;
			}
			int t;
			cin >> t;
			while (t--)
			{
				int x, y;
				cin >> x >> y;
				x++;
				y++;
				g[id(i, j)].push_back(id(x, y));
				deg[id(x, y)]++;
			}
		}
	}
	mf.init();
	queue<int> q;
	rep(i, 1, n * m) if (!deg[i]) q.push(i);
	int tot = 0;
	while (!q.empty())
	{
		int x;
		x = q.front();
		d[x] = ++tot;
		t[tot] = x;
		// debug(x);
		q.pop();
		for (auto v : g[x])
		{
			deg[v]--;
			if (!deg[v])
				q.push(v);
		}
	}
	int sum = 0;
	rep(i, 1, tot)
	{
		if (s[t[i]] > 0)
		{
			sum += s[t[i]];
			mf.addedge(tot + 1, i, s[t[i]]);
		}
		else if (s[t[i]] < 0)
			mf.addedge(i, tot + 2, -s[t[i]]);
		for (auto v : g[t[i]])
			if (d[v])
			{
				mf.addedge(d[v], i, INF);
				debug(i, v);
			}
	}
	mf.S = tot + 1;
	mf.T = mf.n = tot + 2;
	mf.dinic();
	debug(sum, mf.maxflow);
	cout << sum - mf.maxflow << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	freopen("pvz.in","r",stdin);
	freopen("pvz.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}