链接：BZOJ2893
题意
给定一个有向图，以及每次行走的起点终点集合。每次只能在起点集合开始，终点集合结束。求最少多少次行走可以覆盖每个节点。
思路
先吐槽下白学家出题人……
不过话说回来，这个题还是很好的。至少暴露了我对上下界网络流理解的几个问题。
首先我看到这个题，就想到了[AHOI2014]支线剧情。
当时的思路如下：
每个点拆成2个，赋节点流量下界1，上界inf，费用0. 原来的边下界0，上界inf，费用0. 加入点p, q，所有起点从p连来，终点连向q. 连边 $q \rightarrow p$ ，容量下界0，上界inf，费用1，表示每个机器人付出代价1. 求最小费用循环流。
于是直接开始敲，交一发发现WA了。（其实第一发没清空数组还TLE了……）
为什么会WA呢？我检查了40min的代码，甚至怀疑我的zkw费用流写错了，然而用Diff工具对比了下并没有写错。
一定是思路的问题。我找了下题解。大多数人都是上下界最小流建图。每个人说的第一句话就是“显然要缩点”。为啥啊……难道网络流还要求DAG？
后来我才想明白了。无论是最小流，还是最小费用可行流，图中都可以包含环流！一个环流是无头无尾的，而且不一定会经过 $q \rightarrow p$ 边！怎么办呢？把环缩掉！这样就可以强制经过 $q \rightarrow p$ 边了。
其实我们是在 $q \rightarrow p$ 边加代价，这和最小流是等价的……
代码
记得算内存限制！！！！不要卡着256MB开数组！
费用流：
#include <bits/stdc++.h>
#define rep(i, x) for(int i = 1; i <= (x); i++)
#define CLEAR(x) memset((x), 0, sizeof(x))
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e3 + 12;
const int MAXM = MAXN * MAXN / 2 + 10;
namespace MCMF {
struct Edge {
int u, v, flow, cap, cost, next;
};
int s, t, MaxFlow, MinCost, e_ptr = 1, head[MAXN+10]; Edge E[(MAXM+10)<<1];
int vis[MAXN+10], inq[MAXN+10], dist[MAXN+10];
void AddEdge(int u, int v, int cap, int cost) {
E[++e_ptr] = (Edge) { u, v, 0, cap, cost, head[u] }; head[u] = e_ptr;
E[++e_ptr] = (Edge) { v, u, 0, 0, -cost, head[v] }; head[v] = e_ptr;
}
bool spfa() {
queue<int> Q;
memset(dist, 0x3f, sizeof(dist));
Q.push(t); dist[t] = 0; inq[t] = true;
while(!Q.empty()) {
int u = Q.front(); Q.pop(); inq[u] = false;
for(int j=head[u]; j; j=E[j].next) {
int v = E[j].v, f = E[j^1].flow, c = E[j^1].cap, len = E[j^1].cost;
if(f < c && dist[v] > dist[u] + len) {
dist[v] = dist[u] + len;
if(!inq[v]) {
Q.push(v);
inq[v] = true;
}
}
}
}
return dist[s] != INF;
}
int dfs(int u, int flow) {
if(u == t || flow == 0) return flow;
int res = flow; vis[u] = true;
for(int j=head[u]; j; j=E[j].next) {
int v = E[j].v, f = E[j].flow, c = E[j].cap, len = E[j].cost;
if(!vis[v] && dist[v] == dist[u] - len) {
int aug = dfs(v, min(res, c-f));
E[j].flow += aug;
E[j^1].flow -= aug;
res -= aug;
}
}
return flow - res;
}
void zkw() {
int CurFlow = 0;
while(spfa()) {
while(memset(vis, 0, sizeof(vis)),
CurFlow = dfs(s, INF)) {
MaxFlow += CurFlow;
MinCost += CurFlow * dist[s];
}
}
}
void Clear() {
s = t = MaxFlow = MinCost = 0; e_ptr = 1;
CLEAR(head); CLEAR(vis); CLEAR(inq); CLEAR(dist);
}
}
namespace Tarjan {
struct Edge { int v, next; };
int n, e_ptr = 1, head[MAXN+10]; Edge E[(MAXM+10)<<1];
int dfs_clock, scc_cnt, low[MAXN+10], dfn[MAXN+10], sccno[MAXN+10];
void AddEdge(int u, int v) {
E[++e_ptr] = (Edge) { v, head[u] }; head[u] = e_ptr;
}
stack<int> st;
void DFS(int u) {
dfn[u] = low[u] = ++dfs_clock;
st.push(u);
for(int j=head[u]; j; j=E[j].next) {
int v = E[j].v;
if(!dfn[v]) {
DFS(v);
low[u] = min(low[u], low[v]);
} else if(!sccno[v])
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
int v;
++scc_cnt;
do {
v = st.top();
st.pop();
sccno[v] = scc_cnt;
} while(v != u);
}
}
void SCC() {
for(int i = 1; i <= n; i++)
if(!dfn[i]) DFS(i);
}
void Clear() {
n = 0, e_ptr = 1, CLEAR(head);
dfs_clock = scc_cnt = 0;
CLEAR(low); CLEAR(dfn); CLEAR(sccno);
while(!st.empty()) st.pop();
}
}
int T, n, m, a, b, p, q, exf[MAXN+10], vis[MAXN+10];
int St[MAXN+10], Ed[MAXN+10];
inline int readint() {
int f=1, r=0; char c=getchar();
while(!isdigit(c)) { if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)) { r=r*10+c-'0'; c=getchar(); }
return f*r;
}
void Init() {
using Tarjan::sccno;
using Tarjan::scc_cnt;
int u, v;
n = readint(); m = readint();
a = readint(); b = readint();
p = MAXN - 3; q = MAXN - 2;
MCMF::s = MAXN - 1; MCMF::t = MAXN;
rep(i, a) St[i] = readint();
rep(i, b) Ed[i] = readint();
rep(i, m) {
u = readint(); v = readint();
Tarjan::AddEdge(u, v);
}
Tarjan::n = n;
Tarjan::SCC();
CLEAR(vis);
rep(i, n) {
u = sccno[i];
if(vis[u]) continue;
vis[u] = true;
exf[u + scc_cnt]++; exf[u]--;
MCMF::AddEdge(u, u + scc_cnt, INF, 0);
}
for(u = 1; u <= n; u++)
for(int j=Tarjan::head[u]; j; j=Tarjan::E[j].next) {
v = Tarjan::E[j].v;
if(sccno[u] == sccno[v])
continue;
MCMF::AddEdge(sccno[u] + scc_cnt, sccno[v], INF, 0);
}
CLEAR(vis);
rep(i, a) {
u = sccno[St[i]];
if(vis[u]) continue;
vis[u] = true;
MCMF::AddEdge(p, u, INF, 0);
}
CLEAR(vis);
rep(i, b) {
u = sccno[Ed[i]];
if(vis[u]) continue;
vis[u] = true;
MCMF::AddEdge(u+scc_cnt, q, INF, 0);
}
MCMF::AddEdge(q, p, INF, 1);
rep(i, 2*scc_cnt) {
if(exf[i] > 0) MCMF::AddEdge(MCMF::s, i, exf[i], 0);
if(exf[i] < 0) MCMF::AddEdge(i, MCMF::t, -exf[i], 0);
}
}
void Work() {
using namespace MCMF;
zkw();
for(int j=head[s]; j; j=E[j].next)
if(E[j].flow != E[j].cap)
goto fail;
for(int j=head[t]; j; j=E[j].next)
if(E[j^1].flow != E[j^1].cap)
goto fail;
// not fail
printf("%d\n", MinCost); return;
fail: puts("no solution"); return;
}
void Clear() {
n = m = a = b = p = q = 0;
CLEAR(exf); CLEAR(St); CLEAR(Ed); CLEAR(vis);
MCMF::Clear(); Tarjan::Clear();
}
int main() {
T = readint();
while(T--) {
Init(); Work(); Clear();
}
}
最小流：
#include <bits/stdc++.h>
#define rep(i, x) for(int i = 1; i <= (x); i++)
#define CLEAR(x) memset((x), 0, sizeof(x))
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e3 + 12;
const int MAXM = MAXN * MAXN / 2 + 10;
namespace Maxflow {
struct Edge {
int v, flow, cap, next;
};
int s, t, e_ptr = 1, head[MAXN+10]; Edge E[(MAXM+10)<<1];
int d[MAXN+10];
void AddEdge(int u, int v, int cap) {
E[++e_ptr] = (Edge) { v, 0, cap, head[u] }; head[u] = e_ptr;
E[++e_ptr] = (Edge) { u, 0, 0, head[v] }; head[v] = e_ptr;
}
bool BFS() {
queue<int> Q;
memset(d, 0xff, sizeof(d));
d[s] = 0; Q.push(s);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int j=head[u]; j; j=E[j].next) {
int v = E[j].v, f = E[j].flow, c = E[j].cap;
if(f < c && d[v] == -1) {
d[v] = d[u] + 1;
if(v == t) return true;
else Q.push(v);
}
}
}
return false;
}
int DFS(int u, int flow) {
if(u == t || flow == 0) return flow;
int res = flow;
for(int j=head[u]; j; j=E[j].next) {
int v = E[j].v, f = E[j].flow, c = E[j].cap;
if(f < c && d[v] == d[u] + 1) {
int aug = DFS(v, min(res, c-f));
E[j].flow += aug; E[j^1].flow -= aug;
res -= aug;
}
}
return flow - res;
}
int Dinic() {
int MaxFlow = 0, CurFlow = 0;
while(BFS()) {
while( (CurFlow = DFS(s, INF)) )
MaxFlow += CurFlow;
}
return MaxFlow;
}
void Clear() {
s = t = 0; e_ptr = 1;
CLEAR(head); CLEAR(d);
}
}
namespace Tarjan {
struct Edge { int v, next; };
int n, e_ptr = 1, head[MAXN+10]; Edge E[(MAXM+10)<<1];
int dfs_clock, scc_cnt, low[MAXN+10], dfn[MAXN+10], sccno[MAXN+10];
void AddEdge(int u, int v) {
E[++e_ptr] = (Edge) { v, head[u] }; head[u] = e_ptr;
}
stack<int> st;
void DFS(int u) {
dfn[u] = low[u] = ++dfs_clock;
st.push(u);
for(int j=head[u]; j; j=E[j].next) {
int v = E[j].v;
if(!dfn[v]) {
DFS(v);
low[u] = min(low[u], low[v]);
} else if(!sccno[v])
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
int v;
++scc_cnt;
do {
v = st.top();
st.pop();
sccno[v] = scc_cnt;
} while(v != u);
}
}
void SCC() {
for(int i = 1; i <= n; i++)
if(!dfn[i]) DFS(i);
}
void Clear() {
n = 0, e_ptr = 1, CLEAR(head);
dfs_clock = scc_cnt = 0;
CLEAR(low); CLEAR(dfn); CLEAR(sccno);
while(!st.empty()) st.pop();
}
}
int T, n, m, a, b, p, q, exf[MAXN+10], vis[MAXN+10];
int St[MAXN+10], Ed[MAXN+10];
inline int readint() {
int f=1, r=0; char c=getchar();
while(!isdigit(c)) { if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)) { r=r*10+c-'0'; c=getchar(); }
return f*r;
}
void Init() {
using Tarjan::sccno;
using Tarjan::scc_cnt;
int u, v;
n = readint(); m = readint();
a = readint(); b = readint();
p = MAXN - 3; q = MAXN - 2;
Maxflow::s = MAXN - 1; Maxflow::t = MAXN;
rep(i, a) St[i] = readint();
rep(i, b) Ed[i] = readint();
rep(i, m) {
u = readint(); v = readint();
Tarjan::AddEdge(u, v);
}
Tarjan::n = n;
Tarjan::SCC();
CLEAR(vis);
rep(i, n) {
u = sccno[i];
if(vis[u]) continue;
vis[u] = true;
exf[u + scc_cnt]++; exf[u]--;
Maxflow::AddEdge(u, u + scc_cnt, INF);
}
for(u = 1; u <= n; u++)
for(int j=Tarjan::head[u]; j; j=Tarjan::E[j].next) {
v = Tarjan::E[j].v;
if(sccno[u] == sccno[v])
continue;
Maxflow::AddEdge(sccno[u] + scc_cnt, sccno[v], INF);
}
CLEAR(vis);
rep(i, a) {
u = sccno[St[i]];
if(vis[u]) continue;
vis[u] = true;
Maxflow::AddEdge(p, u, INF);
}
CLEAR(vis);
rep(i, b) {
u = sccno[Ed[i]];
if(vis[u]) continue;
vis[u] = true;
Maxflow::AddEdge(u+scc_cnt, q, INF);
}
rep(i, 2*scc_cnt) {
if(exf[i] > 0) Maxflow::AddEdge(Maxflow::s, i, exf[i]);
if(exf[i] < 0) Maxflow::AddEdge(i, Maxflow::t, -exf[i]);
}
Maxflow::AddEdge(q, p, INF); // add this last
}
void Work() {
using namespace Maxflow;
int Ans = 0;
Dinic();
for(int j=head[s]; j; j=E[j].next)
if(E[j].flow != E[j].cap)
goto fail;
for(int j=head[t]; j; j=E[j].next)
if(E[j^1].flow != E[j^1].cap)
goto fail;
// not fail
s = q; t = p;
Ans = E[head[q]].flow;
head[q] = E[head[q]].next; head[p] = E[head[p]].next;
Ans -= Dinic();
printf("%d\n", Ans); return;
fail: puts("no solution"); return;
}
void Clear() {
n = m = a = b = p = q = 0;
CLEAR(exf); CLEAR(St); CLEAR(Ed); CLEAR(vis);
Maxflow::Clear(); Tarjan::Clear();
}
int main() {
T = readint();
while(T--) {
Init(); Work(); Clear();
}
}
