专栏文章

网络流与分治 2025.6.27

cchenzhiyv
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip10oey
此快照首次捕获于
2025/12/03 04:24
3 个月前
此快照最后确认于
2025/12/03 04:24
3 个月前
查看原文
博客

最大流

反对称性：𝑓(𝑥→𝑦)=−𝑓(𝑦→𝑥)𝑓(𝑥→𝑦)=−𝑓(𝑦→𝑥)
流量限制：𝑓(𝑥→𝑦)≤𝑐(𝑥→𝑦)𝑓(𝑥→𝑦)≤𝑐(𝑥→𝑦)
流量平衡：除了 𝑆,𝑇 以外，入流 = 出流
CF1250K
首先，我们想得到一个充要条件，但证明一般比较困难，所以考虑证明必要条件再证充分条件

退流

之前我们对于残量网络进行的唯一操作就是“增广”，每次增广都会增加 𝑆→𝑇 的流量。但是事实上，增加的流量并不一定要是正数：可以搜索一条路径上流量都能减少的路径，然后将路径上的流量都减少 1，得到的仍然是合法的流、合法的残量网络。

二分图匹配

CF1684G
在构造方案时，要注意更据值的性质，进行二分图的分类。

Dinic的实现细节

注意在 Dinic 实现时，可用 vector 来存图，这样内存访问连续，可以减小常数

费用流与最小割

有一个叫Primal Dual 的算法，具体见博客
同时，最小割=最大流
最小割的方案只能用最大流求出，在求出最大流后在残量网络上从s开始进行dfs，得到最大可达集，在在总图中将这一部分减去，剩下的就是最小割的方案。
原因：
  1. 求出来的一定是一个合法的割。
  2. 这个割的权值等于最大流，因为只有当边流满了才不会在残量网络上继续流

最小割的通法

upd:最小割模型： 一些点，选了有收益，不选有代价就是最小割问题，具体见OI-WIKI
最小割本质上就是01整数规划，本质上就是将问题转化为 xi and¬ xj{\large x_i \ and \neg \ x_j } 的形式，然后连边
第一步：将问题目标与最小割 0-1 整数规划模型（就是上面的）进行比对，设出布尔变量。
第二步：将问题的限制与 0-1 整数规划模型的限制（𝑥𝑖 𝑎𝑛𝑑 ¬ 𝑥𝑗𝑥_𝑖 \ 𝑎𝑛𝑑 \ ¬ \ 𝑥_𝑗 ）进行比对，并进行连边，注意连向源/汇点的边是选还是不选。
例子：
P8215
首先，设出布尔变量为每一个人愿不愿意
然后，将割中与源点在一起的人定义为愿意合作，与汇点在一起的人定义为不愿合作，这两种边的流量都是两种情况的不满意度。
即 add(s,i,d) add(i,t,c)add(s,i,d) \ add(i,t,c)，dd、cc含义与题目相同（手模一下即可）
在一个队内，当 xix_i 愿意（值为1）但是 xjx_j 不愿意（值为0）时，满足了模型的 xi and ¬ xjx_i \ and \ \neg \ x_j，所以直接从 xix_i 向 xjx_j 连一条权值为 eie_i 的边，反之同理
此时要表示队伍，所以新建一个点，向一个队伍里的两个人连一条流量为 infinf 的边，可以发现这个点一定在与之相连的点在同一个割里，所以就可以用来表示这个队伍是否合作。
当 AA 喜欢 BB 时:
  1. 依据 xi and ¬ xjx_i \ and \ \neg \ x_j ，因为此时 AA 不合作，所以 AA 所在的队伍是 xjx_j ，所以是 BB 向 AA 所在的队伍连一条值为 aia_i 的边。
  2. 当 AA 选择了不愿意，依据 xi and ¬ xjx_i \ and \ \neg \ x_j ， AA 是 xix_i 所以是 AA 向 BB 所在的队伍连一条值为 bib_i 边
CPP
#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e4+10,inf=5e17;
int n,m;
int cnt;
int h[N<<1],to[N<<4],ne[N<<4],w[N<<4],idx=1;
int id[N];
void Add(int u,int v,int c)
{
	to[++idx]=v;
	w[idx]=c;
	ne[idx]=h[u];
	h[u]=idx;
}
void add(int u,int v,int c)
{
	Add(u,v,c);
	Add(v,u,0);
}
int s,t;
int cur[N<<1],dep[N<<1];
bool bfs()
{
	queue<int> q;
	memset(dep,0,sizeof(dep));
//	for(int i=1;i<=cnt;i++)
//		dep[i]=0;
	dep[s]=1;
	q.emplace(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=ne[i])
		{
			int v=to[i];
			if(w[i]&&!dep[v])
			{
				dep[v]=dep[u]+1;
				q.emplace(v);
			}
		}
	}
	return dep[t];
}
int dfs(int u,int flow)
{
	if(u==t||!flow)
		return flow;
	int tmp=0;
	for(int &i=cur[u];i;i=ne[i])
	{
		int v=to[i];
		if(dep[v]==dep[u]+1&&w[i])
		{
			int d=dfs(v,min(w[i],flow-tmp));
			if(!d)
				dep[v]=0;
			w[i]-=d;
			w[i^1]+=d;
			tmp+=d;
			if(tmp==flow)
				break;
		}
	}
	return tmp;
}
int dinic()
{
	int ans=0;
	while(bfs())
	{
		for(int i=1;i<=cnt;i++)
			cur[i]=h[i];
		int d=dfs(s,inf);
		while(d)
		{
			ans+=d;
			d=dfs(s,inf);
		}
	}
	return ans;
}
signed main()
{
	cin>>n>>m;
	cnt=n<<1;
	s=++cnt;
	t=++cnt;
	for(int i=1,c,d,e;i<=(n<<1);i++)
	{
		cin>>c>>d>>e;
		add(s,i,d);
		add(i,t,c);
		add(i,i&1?i+1:i-1,e);
		if(i&1)
		{
			cnt++;
			id[i]=id[i+1]=cnt;
			add(id[i],i,inf);
			add(id[i+1],i+1,inf);
		}
	}
	for(int i=1,A,B,a,b;i<=m;i++)
	{
		cin>>A>>B>>a>>b;
		add(B,id[A],a);
		add(id[B],A,b);
	}
	cout<<dinic()<<endl;
	return 0;
}
然后在这个图上跑最大流，最小割就是答案
P3227 P6054
这种题设变量，满足式子的思路与上一道题一样，需要注意的是设布尔变量时可以设成 xi,jx_{i,j} 表示 xi≤jx_i \le j 是否成立
P4313
这道题将向邻的数相同的限制条件用一个新的节点来表示
ARC142E
这个可以转化 xi and xjx_i \ and \ x_j 的形式，但是这个并不符合我们们的 xi and ¬xjx_i \ and \ \neg x_j 的形式，所以我们考虑将一边全部取反，同时，观察到这个图可以划分成一个二分图，所以我们将二分图的一边全部取反，就转化为我们熟悉的问题

流和割的模拟

这个要具体问题具体分析，用数据结构加上分类讨论来避免网络流

分治思想

将分治的思想运用到题目中
P7115
这道题我们先构造出两种颜色，三根柱子的方案，然后分治，每次都用这个方法解决问题。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...