如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
先求一次最大流若流量不小于 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');
}
}