网络流学习
https://www.cnblogs.com/SYCstudio/p/7260613.html
https://cn.vjudge.net/contest/282008#discuss
https://www.cnblogs.com/LUO77/p/6115057.html
最大流 Dinic
由于基本上都是看着博客一步一步来的, 没有什么自己的想法, 但是不记录的话下次又没地方看, 所以稍微概括一下
- 建图
- 原图中一条有向边对应新图的这条边 + 边权为 (0) 的反边
- 注意边从 (0) 开始标号, 目的为方便获取反边
- 判断还有无增广路
- 用 BFS 建立分层图 & 判断, 具体为若这条边有流, 且对面的点未分层, 则
lev[v] = lev[u] + 1
- 用 BFS 建立分层图 & 判断, 具体为若这条边有流, 且对面的点未分层, 则
- 计算增广的流量, 并更新网络
- 用 DFS 递归来找流, 具体为
DFS(u, t, nowf)表示当前点, 汇点, 当前上限, 走分层差1且有流的边, 到汇点直接返回值, 正反边更新
- 用 DFS 递归来找流, 具体为
- 不断循环上述两步, 将每次增广的流量加入答案, 知道无增广路
// 搭配飞行员(二分图)
int n, m, S, T;
const int MAXN = 110, MAXM = MAXN * MAXN; // note x2
int cur[MAXN], head[MAXN] ,nume;
struct Adj { int nex, to; LL w; } adj[MAXM << 1];
void addedge(int from, int to, LL w)
{
adj[nume] = (Adj) { head[from], to, w } ;
head[from] = nume ++;
}
namespace Dinic
{
void link(int u, int v, LL w)
{
addedge(u, v, w);
addedge(v, u, 0);
}
const LL INF = 1e10;
int lev[MAXN];
queue <int> q;
bool BFS(int s, int t)
{
memset(lev, 0, sizeof lev);
while (!q.empty()) q.pop();
q.push(s);
lev[s] = 1;
while (!q.empty())
{
int u = q.front(); q.pop();
for (int i = head[u]; i != -1; i = adj[i].nex)
{
int v = adj[i].to;
if (lev[v] || adj[i].w == 0) continue;
lev[v] = lev[u] + 1;
q.push(v);
}
}
return (lev[t] != 0);
}
LL DFS(int u, int t, LL nowf)
{
if (u == t) return nowf;
LL sum = 0;
for (int & i = cur[u]; i != -1; i = adj[i].nex)
{
LL v = adj[i].to;
if (lev[v] != lev[u] + 1 || adj[i].w == 0) continue;
int nowv = DFS(v, t, min(adj[i].w, nowf - sum));
sum += nowv;
adj[i].w -= nowv;
adj[i ^ 1].w += nowv;
if (sum == nowf) break;
}
return sum;
}
LL Dinic(int s, int t)
{
LL ret = 0;
while (BFS(s, t))
{
for (int i = 0; i <= n + 1; ++ i) cur[i] = head[i];
LL nowflow = DFS(s, t, INF);
ret += nowflow;
}
return ret;
}
}
void build()
{
S = 0, T = n + 1;
for (int i = 1; i <= m; ++ i) Dinic::link(S, i, 1);
for (int i= m + 1; i <= n; ++ i) Dinic::link(i, T, 1);
int a, b;
while (scanf("%d%d", &a, &b) != EOF && a != -1)
{
Dinic::link(a, b, 1);
}
}
int main()
{
m = in();
n = in();
memset(head, -1, sizeof head);
build();
int ans = Dinic::Dinic(S, T);
if (ans == 0) return puts("No Solution!"), 0;
printf("%d
", ans);
for (int u = 1; u <= m; ++ u)
for (int i = head[u]; i != -1; i = adj[i].nex)
if (adj[i].to > m && adj[i].w == 0) printf("%d %d
", u, adj[i].to);
return 0;
}
/*
*/
https://blog.csdn.net/clove_unique/article/details/54884437
搭配飞行员 <二分图 + 方案>
题意: 如题
Sol:
源点汇点分别向两块连边, 然后题目中给定的连边, 边权都是 (1)
跑最大流即可
输出方案若两块间连边流掉了, 那么就一定选了这条边, 因为 Dinic 流程中都是更正为实际流量的, 不会存在错误的流量, 要不然最大流也算不对
模板代码
最小费用最大流 Dinic + SPFA
https://www.cnblogs.com/fzl194/p/8859308.html
还是概括...
- 最大流是定值
- 不管怎么增广, 增广到不行为止, 一定能得到最大流
- 那么沿着(单价的和)最短路增广就可以满足最大流下最小费用
int n, m, S, T;
const int MAXN = 5e3 + 10, MAXM = 5e4 + 10; // note x2
int head[MAXN] ,nume;
struct Adj { int nex, to; LL w, c; } adj[MAXM << 1];
void addedge(int from, int to, LL w, LL c)
{
adj[nume] = (Adj) { head[from], to, w, c } ;
head[from] = nume ++;
}
typedef pair<LL, LL> PLL;
#define mkpr make_pair
#define fir first
#define sec second
namespace MCMF
{
void link(int u, int v, LL w, LL c)
{
addedge(u, v, w, c);
addedge(v, u, 0, -c);
}
const LL INF = 1e10, INFD = 1e10;
int pre[MAXN];
LL dis[MAXN], f[MAXN];
bool inq[MAXN];
queue <int> q;
bool SPFA(int s, int t)
{
for (int i = 1; i <= n; ++ i) dis[i] = INFD, inq[i] = false;
while (!q.empty()) q.pop();
q.push(s); dis[s] = 0; inq[s] = true; f[s] = INF;
while (!q.empty())
{
int u = q.front(); q.pop();
for (int i = head[u]; i != -1; i = adj[i].nex)
{
int v = adj[i].to; LL c = adj[i].c;
if (dis[u] + c < dis[v] && adj[i].w > 0)
{
dis[v] = dis[u] + c;
pre[v] = i ^ 1;
f[v] = min(f[u], adj[i].w);
if (!inq[v]) inq[v] = true, q.push(v);
}
}
inq[u] = false;
}
return (dis[t] != INFD);
}
PLL MCMF(int s, int t)
{
LL flow = 0, cost = 0;
while (SPFA(s, t))
{
flow += f[t];
cost += f[t] * dis[t];
int now = t;
while (now != s)
{
adj[pre[now] ^ 1].w -= f[t];
adj[pre[now]].w += f[t];
now = adj[pre[now]].to;
}
}
return mkpr(flow, cost);
}
}
void build()
{
S = in(); T = in();
for (int i = 1; i <= m; ++ i)
{
int u = in(), v = in(); LL w = in(), c = in();
MCMF::link(u, v, w, c);
}
}
int main()
{
n = in(); m = in();
memset(head, -1, sizeof head);
build();
PLL ans = MCMF::MCMF(S, T);
printf("%lld %lld
", ans.fir, ans.sec);
return 0;
}
最小路径覆盖
要求选尽量少的不相交路径, 覆盖所有点
Sol:
本来每个点需要一条路径, 连接一对点, 即可减少一条路径,
所以拆成出点入点, 二分图最大匹配
输出方案注意一下