网络流
最大流
网络流时间复杂度大约为$O(n^2m)$
不过也比较玄学罢了
将一张图建完之后直接跑$dinic$即可
接下来有封装之后的版本
注意这个封装版本的最大流应该有以下的特征：
首先最大流这个点我们是从$1$开始的，因此我们在设置对应的起点和终点的时候，应该注意设置
其次是边的标号，因为是从$0$开始的
所以我们每次开始的边其实都是$etot$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int V = 1210;
const int E = 121000;
template<typename T>
struct FlowGraph
{
int s,t,vtot;
int head[V],etot;
int dis[V],cur[V];
struct edge
{
int v,nxt;
T f;
}e[E * 2];
void addedge(int u,int v,T f)
{
e[etot] = {v,head[u],f}; head[u] = etot++;
e[etot] = {u,head[v],0}; head[v] = etot++;
}
bool bfs()
{
for(int i = 1;i <= vtot;++i)
{
dis[i] = 0;
cur[i] = head[i];
}
queue<int> q;
q.push(s);dis[s] = 1;
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = head[u];~i;i = e[i].nxt)
{
if(e[i].f && !dis[e[i].v])
{
int v = e[i].v;
dis[v] = dis[u] + 1;
if(v == t) return true;
q.push(v);
}
}
}
return false;
}
T dfs(int u,T m)
{
if(u == t) return m;
T flow = 0;
for(int i = cur[u];~i;cur[u] = i = e[i].nxt)
{
if(e[i].f && dis[e[i].v] == dis[u] + 1)
{
T f = dfs(e[i].v,min(e[i].f,m));
e[i].f -= f;
e[i ^ 1].f += f;
m -= f;
flow += f;
if(!m) break;
}
}
if(!flow) dis[u] = -1;
return flow;
}
T dinic()
{
T flow = 0;
while(bfs()) flow += dfs(s,numeric_limits<T>::max());
return flow;
}
void init(int s_,int t_,int vtot_)
{
s = s_;
t = t_;
vtot = vtot_;
etot = 0;
for(int i = 1;i <= vtot;++i) head[i] = -1;
}
};
int n,m,s,t;
FlowGraph<ll> g;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m >> s >> t;
g.init(s,t,n);
for(int i = 1,u,v,w;i <= m;++i)
{
cin >> u >> v >> w;
g.addedge(u,v,w);
}
cout << g.dinic() << "\n";
return 0;
}方案分配
方案分配实际上我们可以思考他的流量和之前的关系，然后我们判断这个流量来输出方案
题目条件可以是类似于这样子的，给定一些试题类型，其中再给定一些试题，我每个试题是属于不同的试题类型的，求是否可以分配，并且输出方案
那么其实我们对应的解决方案是把相对应的东西放到一个$vector$中，然后去判断对应的边的流量即可
P2763
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int V = 1210;
const int E = 121000;
template<typename T>
struct FlowGraph
{
int s,t,vtot;
int head[V],etot;
int dis[V],cur[V];
struct edge
{
int v,nxt;
T f;
}e[E * 2];
void addedge(int u,int v,T f)
{
e[etot] = {v,head[u],f}; head[u] = etot++;
e[etot] = {u,head[v],0}; head[v] = etot++;
}
bool bfs()
{
for(int i = 1;i <= vtot;++i)
{
dis[i] = 0;
cur[i] = head[i];
}
queue<int> q;
q.push(s);dis[s] = 1;
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = head[u];~i;i = e[i].nxt)
{
if(e[i].f && !dis[e[i].v])
{
int v = e[i].v;
dis[v] = dis[u] + 1;
if(v == t) return true;
q.push(v);
}
}
}
return false;
}
T dfs(int u,T m)
{
if(u == t) return m;
T flow = 0;
for(int i = cur[u];~i;cur[u] = i = e[i].nxt)
{
if(e[i].f && dis[e[i].v] == dis[u] + 1)
{
T f = dfs(e[i].v,min(e[i].f,m));
e[i].f -= f;
e[i ^ 1].f += f;
m -= f;
flow += f;
if(!m) break;
}
}
if(!flow) dis[u] = -1;
return flow;
}
T dinic()
{
T flow = 0;
while(bfs()) flow += dfs(s,numeric_limits<T>::max());
return flow;
}
void init(int s_,int t_,int vtot_)
{
s = s_;
t = t_;
vtot = vtot_;
etot = 0;
for(int i = 1;i <= vtot;++i) head[i] = -1;
}
};
int n,k,s,t;
FlowGraph<ll> g;
struct node
{
int st,num,id;
};
vector<int> prob[100];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> k >> n;
s = n + k + 1;
t = n + k + 2;
g.init(s,t,t + 10);
int sum = 0;
for(int i = 1,x;i <= k;++i)
{
//1 -> type
cin >> x;
sum += x;
g.addedge(s,i,x);
}
// cout << "sum -> " << sum << "\n";
vector<node> used;
for(int i = 1;i <= n;++i)
{
//type + 1 -> type + n
int num;
cin >> num;
for(int j = 1,bel;j <= num;++j)
{
cin >> bel;
used.push_back({bel,i,g.etot});
g.addedge(bel,k + i,1);
}
}
for(int i = 1;i <= n;++i)
{
g.addedge(k + i,t,1);
}
// cout << "??\n";
ll namomo = g.dinic();
if(namomo != sum)
{
cout << "\n";
}
else
{
for(auto now:used)
{
int idd = now.id;
if(g.e[idd].f == 0)
{
prob[now.st].push_back(now.num);
}
}
for(int i = 1;i <= k;++i)
{
cout << i << ":";
for(auto to:prob[i])
{
cout << " " << to;
}
cout << "\n";
}
}
return 0;
}
/*
属于是最大流的方案分配问题，首先显而易见我们可以通过这一条边的流量去判断这个边是否被用过
来判断是否属于这一个方案当中
那么我们可以这样子，因为我们是把试题库和相对应的试题连接在一起
ok，那么这样子我们在建边的时候我们可以把相对应的边的号给放到一个vector里面
然后后续我们去检查这个边的流量是否为1即可
*/路径模型
比如说一个序列，如果可以从$a_i$ 到$a_j$有一条路径，实际上我们也可以映射到一张图上面去考虑，因为我们在做最大流的过程中实际上就是在走一些流的路径
然后对于一些流量限制的情况下我们可以采用拆点的方法去限制流量
P2776
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int V = 101210;
const int E = 1210000;
const int maxn = 5e2 + 10;
template<typename T>
struct FlowGraph
{
int s,t,vtot;
int head[V],etot;
int dis[V],cur[V];
struct edge
{
int v,nxt;
T f;
}e[E * 2];
void addedge(int u,int v,T f)
{
e[etot] = {v,head[u],f}; head[u] = etot++;
e[etot] = {u,head[v],0}; head[v] = etot++;
}
bool bfs()
{
for(int i = 1;i <= vtot;++i)
{
dis[i] = 0;
cur[i] = head[i];
}
queue<int> q;
q.push(s);dis[s] = 1;
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = head[u];~i;i = e[i].nxt)
{
if(e[i].f && !dis[e[i].v])
{
int v = e[i].v;
dis[v] = dis[u] + 1;
if(v == t) return true;
q.push(v);
}
}
}
return false;
}
T dfs(int u,T m)
{
if(u == t) return m;
T flow = 0;
for(int i = cur[u];~i;cur[u] = i = e[i].nxt)
{
if(e[i].f && dis[e[i].v] == dis[u] + 1)
{
T f = dfs(e[i].v,min(e[i].f,m));
e[i].f -= f;
e[i ^ 1].f += f;
m -= f;
flow += f;
if(!m) break;
}
}
if(!flow) dis[u] = -1;
return flow;
}
T dinic()
{
T flow = 0;
while(bfs()) flow += dfs(s,numeric_limits<T>::max());
return flow;
}
void init(int s_,int t_,int vtot_)
{
s = s_;
t = t_;
vtot = vtot_;
etot = 0;
for(int i = 1;i <= vtot;++i) head[i] = -1;
}
};
int n,m,s,t;
int a[maxn],dp[maxn];
FlowGraph<ll> g;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1;i <= n;++i)
{
cin >> a[i];
dp[i] = 1;
}
int ans = 1;
for(int i = 2;i <= n;++i)
{
for(int j = 1;j < i;++j)
{
if(a[i] >= a[j])
{
dp[i] = max(dp[i],dp[j] + 1);
}
}
ans = max(ans,dp[i]);
}
cout << ans << "\n";
s = 2 * n + 1;
t = 2 * n + 2;
g.init(s,t,t);
for(int i = 1;i <= n;++i)
{
if(dp[i] == 1) g.addedge(s,i,n);//添加流量为inf的边
if(dp[i] == ans) g.addedge(i + n,t,n);
g.addedge(i,i + n,1);
}
for(int i = 1;i <= n;++i)
{
for(int j = i + 1;j <= n;++j)
{
if(a[j] >= a[i] && dp[j] == dp[i] + 1)
{
g.addedge(i + n,j,1);
}
}
}
cout << g.dinic() << "\n";
g.init(s,t,t);
for(int i = 1;i <= n;++i)
{
if(dp[i] == 1) g.addedge(s,i,n);//添加流量为inf的边
if(dp[i] == ans) g.addedge(i + n,t,n);
if(ans == 1) g.addedge(i,i + n,1);
else g.addedge(i,i + n,n);
}
for(int i = 1;i <= n;++i)
{
for(int j = i + 1;j <= n;++j)
{
if(a[j] >= a[i] && dp[j] == dp[i] + 1)
{
g.addedge(i + n,j,1);
}
}
}
cout << g.dinic() << "\n";
}
/*
题目大意：给定一个序列，需要解决如下的三个问题
1.求这个序列的最长非递减子序列
2.每个元素只能使用一次的情况下序列的最长非递减子序列
3.每个元素使用多次的情况下序列的最长非递减子序列
建图思路:首先对于第一个问题来说我们直接dp即可
对于第二个问题，我们需要思考以下我们的建图方向
因为只需要求方案数目，那么我们可以进行这样子的建图，我们可以从s->dp = 1的值建一条边
我们也可以从dp = ans -> t建一条边
因为在第一种情况我们只考虑每一个点使用一个那么我们可以使用拆点
拆点是为了加一个限制只能流一个1
然后因为我们要找第j个数字可能从哪个第i个数字转移过来 那么我们继续找重新建边即可
对于第三个问题 实际上我一个点可以使用多次了
那么我们先特判考虑最后答案是1的情况 其实实际上下面两个问题的答案就是n
然后我们再考虑一个可以使用多次 那么我们拆店的时候对于多个点建n就可以了
*/
最小割
概念: 给定一张图，删除一些边使得$s$和$t$不连通
那么其实就是对于每一个点，我去将点划分为两个集合，每一个点要么属于$s$集合，要么属于$t$集合
那么对于这里割边来说，实际上就是找一条边，对于他的两个端点$u$和$v$，两个点分别属于一个集合
最小割 $\geq$ 最大流
接下来我们分析一下建边的过程
对于无向图建立割边，实际上我们不仅要考虑正向边，我们也要考虑反向边，那么对于无向图的建图方式实际上就是建两条相同边权的边
具体的建边方式如下图所示可以
void addedge(int u,int v,T f,T f2 = 0)
{
e[etot] = {v,head[u],f}; head[u] = etot++;
e[etot] = {u,head[v],f2}; head[v] = etot++;
}那么有向图的话实际上还是和之前的类似，我去建一条长度为$c$的边，另外一条是长度为$0$的边
如何在实际题目中去思考到 最小割 这个东西呢？
最大权独立集
首先我们可以考虑引入这样子的一个问题
假设我们有两个集合(假设为一个黑子集合和一个白子集合)，每个集合都有$n$个点，每个点都有一个点权，如果我们取了一些黑子那么我们就不能取白子，要求我们最后取得的权值最大 ，对于这一个问题我们如何解答呢？
我们可以考虑这样子的一个解题方向，我们最后的集合一定是分为两个集合，一个集合是取到的棋子，另外一个集合是没有取到的集合。
那么分为两个集合的操作是不是就是一个求最小割的过程呢？我们只需要把两个集合分别和$S$和$T$集合连边就可以，然后接下来相对应连边的权值就是他们的点权，然后点之间的限制因为无法切割我们可以采用$inf$
那么其实对应的如果是二维棋盘我们也可以通过这样子的操作
P2774
方格取数，每个方格有一定权值，可以取若干个方格，方格之间不能有相互重叠的边
本质上也就是求一个最大权独立集的问题，行列相对应建边即可
const ll inf = (1ll << 60);
int n,m,s,t,x;
FlowGraph<ll> g;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m;
s = n * m + 1;
t = n * m + 2;
g.init(s,t,t);
ll ans = 0;
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= m;++j)
{
cin >> x;
ans += x;
int id = (i - 1) * m + j;
if((i + j) % 2 == 1)
{
g.addedge(s,id,x);
if(i - 1 >= 1) g.addedge(id,id - m,inf);
if(i + 1 <= n) g.addedge(id,id + m,inf);
if(j + 1 <= m) g.addedge(id,id + 1,inf);
if(j - 1 >= 1) g.addedge(id,id - 1,inf);
}
else g.addedge(id,t,x);
}
}
cout << ans - g.dinic() << "\n";
return 0;
}
最大权闭合子图
最大权闭合子图的定义实际上就是我每个点有一定的点权，选定一些点需要使得点权和最大，然后如果我选了一个点我是必须需要选定其他后继点的，然后我们来求这张图最多获得多少的点权
其实这个也是最小割的一种模型，那么实际上和最大权独立集的本质是一样的，我给$s$和$t$集合一定的意义，然后我去进行相应的连边。
考虑这样的一件事情，因为我们在求最小割的过程中实际上是求在$S$集合中的最小割，那么实际上也就是我们把一些东西放到了$S$集合上面。
那么之前我们说了边的方案如何选择，那么如何去进行选择点的方案呢？
那么我们可以去看$dis$数组里面的东西，因为$dis$刚开始都是$0$的，对于放在$S$集合里面的东西我们都应该选择$dis$不为$0$的点即可
int n,m,s,t;
FlowGraph<ll> g;
string str;
const ll inf = (1ll << 60);
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> m >> n;
s = m + n + 1;
t = m + n + 2;
g.init(s,t,t);
ll ans = 0;
getline(cin,str);
for(int i = 1;i <= m;++i)
{
getline(cin,str);
stringstream ss;
ss << str;
// cout << "str -> " << str << "\n";
int x;
ss >> x;
g.addedge(s,i,x);//第i个实验的费用
ans += x;
while(!ss.eof())
{
ss >> x;
g.addedge(i,x + m,inf);
}
}
for(int i = 1;i <= n;++i)
{
int x;cin >> x;
g.addedge(i + m,t,x);
}
ans -= g.dinic();
vector<int> p1,p2;
for(int i = 1;i <= m;++i)
{
if(g.dis[i] > 0) p1.push_back(i);
}
for(int i = 1;i <= n;++i)
{
if(g.dis[i + m] > 0) p2.push_back(i);
}
for(auto to:p1) cout << to << " ";
cout << "\n";
for(auto to:p2) cout << to << " ";
cout << "\n";
cout << ans << "\n";
return 0;
}最小费用最大流
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int V = 20100;
const int E = 201000;
template<typename T>
struct MinCostGraph
{
int s,t,vtot;
int head[V],cur[V],etot;
T dis[V],flow,cost;
int pre[V];
bool vis[V];
struct edge
{
int v,nxt;
T f,c;
}e[E * 2];
void addedge(int u,int v, T f, T c, T f2 = 0)
{
e[etot] = {v, head[u], f, c}; head[u] = etot++;
e[etot] = {u, head[v], f2, -c}; head[v] = etot++;
}
bool spfa()
{
T inf = numeric_limits<T>::max() / 2;//防止溢出
for(int i = 1; i <= vtot; ++i)
{
dis[i] = inf;
vis[i] = false;
pre[i] = -1; //记录一下上一条边,方便增广
}
dis[s] = 0;
vis[s] = true;
queue<int> q;
q.push(s);
while(!q.empty())
{
auto u = q.front();
for(int i = head[u]; ~i; i = e[i].nxt)
{
int v = e[i].v;
if(e[i].f && dis[v] > dis[u] + e[i].c)
{
dis[v] = dis[u] + e[i].c;
pre[v] = i;
if(!vis[v])
{
vis[v] = 1;
q.push(v);
}
}
}
q.pop();
vis[u] = false;
}
return dis[t] != inf;
}
//增广
void augment()
{
int u = t;
T f = numeric_limits<T>::max();
while(~pre[u])
{
f = min(f, e[pre[u]].f);
u = e[pre[u] ^ 1].v;
}
flow += f;
cost += f * dis[t];
u = t;
while(~pre[u])
{
e[pre[u]].f -= f;
e[pre[u] ^ 1].f += f;
u = e[pre[u] ^ 1].v;
}
}
pair<T, T> solve()
{
flow = 0;
cost = 0;
while(spfa()) augment();
return {flow, cost};
}
void init(int s_, int t_, int vtot_)
{
s = s_;
t = t_;
vtot = vtot_;
etot = 0;
for(int i = 1; i <= vtot; ++i) head[i] = -1;
}
};
MinCostGraph<int> g;
int n,m,s,t;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m >> s >> t;
g.init(s,t,n);
for(int i = 1,u,v,f,c;i <= m;++i)
{
cin >> u >> v >> f >> c;
g.addedge(u,v,f,c);
}
auto ans = g.solve();
cout << ans.first << " " << ans.second << "\n";
return 0;
}最大费用最大流
因为我们考虑这样子的一件事情，我们在求$MCMF$的时候实际上求的是最小的费用那么我们只需要建负边并且最终答案取反就可以了
P4015
MinCostGraph<ll> g1,g2;
int n,m,s,t;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m;
s = n + m + 1;
t = n + m + 2;
g1.init(s,t,t);
g2.init(s,t,t);
for(int i = 1,x;i <= n;++i)
{
cin >> x;
g1.addedge(s,i,x,0);
g2.addedge(s,i,x,0);
}
for(int i = 1,x;i <= m;++i)
{
cin >> x;
g1.addedge(i + n,t,x,0);
g2.addedge(i + n,t,x,0);
}
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= m;++j)
{
int x;
cin >> x;
g1.addedge(i,j + n,1 << 30,x);
g2.addedge(i,j + n,1 << 30,-x);
}
}
auto ans1 = g1.solve();
auto ans2 = g2.solve();
cout << ans1.second << "\n" << -ans2.second << "\n";
return 0;
}优化建图
题意: 给定$n$个座位，每个座位刚开始有两个数字$1$和$0$，题目保证初始给定的$1$的数量少于$0$的数量，将一个$1$移动位置需要$abs(i - j)$的贡献，问让刚开始的$1$全部变成$0$最少需要多少贡献
解题思路: 其实刚开始看到题目就想着是裸的费用流，将两种点分在两边，中间连接相对应的边权即可，但是后面发现这样子写的话会有问题。但是考虑反正$1$只会往相邻的$0$移动，那么就相邻的两边建边即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int V = 20100;
const int E = 521000;
template<typename T>
struct MinCostGraph
{
int s,t,vtot;
int head[V],cur[V],etot;
T dis[V],flow,cost;
int pre[V];
bool vis[V];
struct edge
{
int v,nxt;
T f,c;
}e[E * 2];
void addedge(int u,int v, T f, T c, T f2 = 0)
{
e[etot] = {v, head[u], f, c}; head[u] = etot++;
e[etot] = {u, head[v], f2, -c}; head[v] = etot++;
}
bool spfa()
{
T inf = numeric_limits<T>::max() / 2;//防止溢出
for(int i = 1; i <= vtot; ++i)
{
dis[i] = inf;
vis[i] = false;
pre[i] = -1; //记录一下上一条边,方便增广
}
dis[s] = 0;
vis[s] = true;
queue<int> q;
q.push(s);
while(!q.empty())
{
auto u = q.front();
for(int i = head[u]; ~i; i = e[i].nxt)
{
int v = e[i].v;
if(e[i].f && dis[v] > dis[u] + e[i].c)
{
dis[v] = dis[u] + e[i].c;
pre[v] = i;
if(!vis[v])
{
vis[v] = 1;
q.push(v);
}
}
}
q.pop();
vis[u] = false;
}
return dis[t] != inf;
}
//增广
void augment()
{
int u = t;
T f = numeric_limits<T>::max();
while(~pre[u])
{
f = min(f, e[pre[u]].f);
u = e[pre[u] ^ 1].v;
}
flow += f;
cost += f * dis[t];
u = t;
while(~pre[u])
{
e[pre[u]].f -= f;
e[pre[u] ^ 1].f += f;
u = e[pre[u] ^ 1].v;
}
}
pair<T, T> solve()
{
flow = 0;
cost = 0;
while(spfa()) augment();
return {flow, cost};
}
void init(int s_, int t_, int vtot_)
{
s = s_;
t = t_;
vtot = vtot_;
etot = 0;
for(int i = 1; i <= vtot; ++i) head[i] = -1;
}
};
MinCostGraph<int> g;
int n,m,s,t;
int a[V];
int main()
{
cin >> n;
s = n + 1,t = n + 2;
g.init(s,t,t);
vector<int> pos0,pos1;
int ct = 0;
for(int i = 1;i <= n;++i)
{
cin >> a[i];
if(a[i])
{
// ct++;
g.addedge(s,i,1,0);
}
else
{
g.addedge(i,t,1,0);
}
}
for(int i = 1;i <= n - 1;++i)
{
g.addedge(i,i + 1,1 << 30,1);
g.addedge(i + 1,i,1 << 30,1);
}
auto [f,c] = g.solve();
cout << c << "\n";
return 0;
}
