Frequency Hopping wu-kan

先求一次最大流若流量不小于 C 则 possible,否则依次把最小割里的弧容量加到 C 再看流量是否大于 C。

蓝书上说这样会 T 但是事实上并没有…加上蓝书上的两个优化也不过只快了一两百 ms 而已。

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9;
struct Graph
{
	struct Vertex
	{
		vector<int> o;
	};
	struct Edge : pair<int, int>
	{
		ll cap;
	};
	vector<Vertex> v;
	vector<Edge> e;
	Graph(int n) : v(n) {}
	void add(const Edge &ed)
	{
		v[ed.first].o.push_back(e.size());
		e.push_back(ed);
	}
};
struct ISAP : Graph
{
	ll flow;
	vector<ll> f;
	vector<int> h, cur, gap;
	ISAP(int n) : Graph(n) {}
	void add(Edge ed)
	{
		Graph::add(ed);
		swap(ed.first, ed.second), ed.cap = 0;
		Graph::add(ed);
	}
	ll dfs(int s, int u, int t, ll r)
	{
		if (r == 0 || u == t)
			return r;
		ll _f, _r = 0;
		for (int &i = cur[u], k; i < v[u].o.size(); ++i)
			if (k = v[u].o[i], h[u] == h[e[k].second] + 1)
			{
				_f = dfs(s, e[k].second, t, min(r - _r, e[k].cap - f[k]));
				f[k] += _f, f[k ^ 1] -= _f, _r += _f;
				if (_r == r || h[s] >= v.size())
					return _r;
			}
		if (!--gap[h[u]])
			h[s] = v.size();
		return ++gap[++h[u]], cur[u] = 0, _r;
	}
	void ask(int s, int t)
	{
		h.assign(v.size(), 0);
		cur.assign(v.size(), 0);
		gap.assign(v.size() + 2, 0);
		for (f.assign(e.size(), flow = 0); h[s] < v.size();)
			flow += dfs(s, s, t, INF);
	}
};
int main()
{
	for (int n, e, c, kase = 0; scanf("%d%d%d", &n, &e, &c) && n;)
	{
		printf("Case %d: ", ++kase);
		ISAP g(n + 1);
		for (ISAP::Edge ed; e--; g.add(ed))
			scanf("%d%d%d", &ed.first, &ed.second, &ed.cap);
		g.ask(1, n);
		if (g.flow >= c)
		{
			printf("possible\n");
			continue;
		}
		vector<int> vis(n + 1, 0), mincut;
		for (deque<int> q(1, vis[1] = 1); !q.empty(); q.pop_front())
			for (int i = 0, u = q.front(), k, second; i < g.v[u].o.size(); ++i)
				if (k = g.v[u].o[i], second = g.e[k].second,
					!vis[second] && g.e[k].cap > g.f[k])
					q.push_back(second), vis[second] = 1;
		for (int i = 0; i != g.e.size(); ++i)
			if (vis[g.e[i].first] && !vis[g.e[i].second] && g.e[i].cap > 0)
				mincut.push_back(i);
		vector<ISAP::Edge> ans;
		for (int i = 0, tmp = c; i < mincut.size(); ++i)
		{
			swap(tmp, g.e[mincut[i]].cap);
			g.ask(1, n);
			if (g.flow >= c)
				ans.push_back(g.e[mincut[i]]);
			swap(tmp, g.e[mincut[i]].cap);
		}
		if (ans.empty())
		{
			printf("not possible\n");
			continue;
		}
		printf("possible option:");
		sort(ans.begin(), ans.end());
		for (int i = 0; i != ans.size(); ++i)
			printf("(%d,%d)%c",
				   ans[i].first, ans[i].second,
				   i + 1 < ans.size() ? ',' : '\n');
	}
}