本网络流24题是根据洛谷tag来列出的，题目传送门acwing题库有该题会加上acwing链接。
$长篇警告$ — $长篇警告$ — $长篇警告$
目录：（13/24）
1.P2756 飞行员配对方案问题(最大流)
2.P2763 试题库问题
3.P2774 方格取数问题
4.P3355 骑士共存问题
5.P4015 运输问题
6.P2764 最小路径覆盖问题
7.P2765 魔术球问题
8.P3254 圆桌问题
9.P4014 分配问题
10.P2761 软件补丁问题
11.P4013 数字梯形问题
12.P4016 负载平衡问题
13.P2770 航空路线问题
待更新
由于9月11号有一个pat甲级，英语还不会，pta的题目还没刷，所以等9月11号考完甲级会更新剩下11道题。
推荐y总 进阶课的网络流
参考博客: 《网络流24题》（23/24）( 部分题建图参考)
网络流推荐博客 ： EK不够快？再学个Dinic吧
究级的最大流算法：ISAP与HLPP
1.P2756 飞行员配对方案问题(最大流)
题目传送门洛谷 P2756 飞行员配对方案问题 ---- acwing 飞行员配对方案问题
m个外籍飞行员，总共n个飞行员
题目就是找到最大匹配，并输出匹配。
那么想到可以使用匈牙利算法（匈牙利大法好，那么自然的匈牙利算法中的match数组记录了匹配，所以直接输出匹配就行
由于是网络流专题，那么自然可以使用网络流，那么就是个很简单的建图方式，使用超级源点连接所有左侧外籍飞行员，所有右侧英国飞行员连接超级汇点，左侧外籍飞行员连接右侧英国飞行员(根据输入连接)，由于一共n个飞行员，所有我习惯将超级原点设为0，超级汇点设为n + 1 ,那么从源点到汇点跑一遍最大流就行，最大流就是匹配数。那么就要考虑如何输出匹配的边，由于使用的是链式前星，所以可以先加入两个飞行员之间的边，记录此时的idx，然后编号是奇数的是反向边，偶数的是正向边，找到编号是奇数的边，并且f[i]是1，代表该边对应的正向边被占用(匹配)，输出这个被占用的边即可。
- 匈牙利算法
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 110,M = 1e4 + 100 ;
int n,m;
int h[N],e[M],ne[M],idx ;
int match[N] ;
int ans[N] ;
bool st[N] ;
void add(int a,int b){ //加边函数
e[idx] = b ,ne[idx] = h[a] ,h[a] = idx++ ;
}
bool find(int u){ //匈牙利算法里面的找到增广路径，递归写法
for(int i = h[u] ;~ i ; i = ne[i]){
int j = e[i] ;
if(st[j]) continue ;
st[j] = 1 ;
int t = match[j] ;
if(t == 0 || find(t)){
match[j] = u ;
return 1 ;
}
}
return 0 ;
}
int main(){
cin >> m >> n ;
int a,b;
memset(h,-1,sizeof h) ;
while(cin >> a >> b , ~ a ){ //加边
add(a,b) ;
}
int cnt = 0;
for(int i = 1 ; i <= m ; i++){
memset(st,0,sizeof st) ;
if(find(i)) cnt ++ ; //找匹配
}
for(int i = 1 ; i <= n ; i++){
if(match[i]) ans[match[i]] = i ;
}
cout << cnt << "\n" ;
for(int i = 1 ; i <= m ; i++) //输出答案
if(ans[i])
cout << i << " " << ans[i] << "\n" ;
return 0;
}
- 最大流 dinic写法
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 110 , M = 1e4 + 100 , INF = 0x3f3f3f3f ;
int n,m;
int h[N],e[M],f[M],ne[M],idx;
int q[N],dep[N] ;
bool st[N] ;
void add(int a,int b){ //加边
e[idx] = b, f[idx] = 1 ,ne[idx] = h[a] ,h[a] = idx ++ ;
e[idx] = a ,f[idx] = 0 ,ne[idx] = h[b] ,h[b] = idx ++ ;
}
bool bfs(){ //bfs找到所有点的dep深度
int hh = 0 ,tt = 0 ;
memset(st,0,sizeof st) ;
memset(dep,0x3f,sizeof dep) ;
q[0] = 0 ,dep[0] = 0 ,st[0] = 1 ;
while(hh <= tt){
int t = q[hh++] ;
for(int i = h[t] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(!st[j] && f[i]){
dep[j] = dep[t] + 1;
st[j] = 1 ;
q[++tt] = j ;
}
}
}
if(dep[m + 1] != 0x3f3f3f3f ) return 1 ;
return 0 ;
}
int dfs(int u ,int d){
if(u == m + 1 ) return d ;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(dep[j] == dep[u] + 1 && f[i]){
int nd ;
if(nd = dfs(j,min(d,f[i]))){
f[i] -= nd ;
f[i ^ 1] += nd ;
return nd ;
}
}
}
return 0 ;
}
int dinic(){
int res = 0 ;
int cnt = 0 ;
while(bfs()){
int t ;
while(t = dfs(0,INF)) res += t ;
}
return res ;
}
int main(){
cin >> n >> m ;
memset(h,-1,sizeof h) ;
int a,b;
while(cin >> a >> b , ~ a){
add(a,b) ;
}
int len = idx ; //记录两个飞行之间的边到的编号，，后面输出边来用
for(int i = 1 ; i <= n ; i++) add(0,i) ;
for(int i = n + 1 ; i <= m ; i++) add(i,m + 1) ;
printf("%d\n",dinic()) ;
for(int i = 0 ; i < len ; i++){
if(i & 1 && f[i]){
cout << e[i] << " " << e[i ^ 1] << "\n" ;
}
}
return 0;
}
2.P2763 试题库问题
题目传送门 洛谷 P2763 试题库问题 — acwing 2181. 试题库问题
建图，由于题目有sp
建立一个超级原点连接所有的题目类型编号容量为需要该类型题目数量，连接所有题目和类型容量为1，代表题目对该类型的贡献为1，连接所有的题目到超级汇点，代表每个题目只能选一个，之后跑一遍最大流就行。
至于输出方案，采取和上一题一样的思路，记录编号，找到使用了的边(在类型和题目编号之间使用了的)，然后记录每种类型所选出的题目，输出即可，，注意判断一下最大流和需要找的题目数量是否相同,不相同证明无解。
- 最大流
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1100 , M = 4e5 + 100 ,K = 50 , INF = 0x3f3f3f3f ;
int k,n,S,T ;
int h[N],e[M],f[M],ne[M],idx ;
int q[N],dep[N] ;
int cnt[N] ;
bool st[N] ;
int sum ;
vector<int> ans[K] ;
void init(){
memset(h,-1,sizeof h) ;
}
void add(int a,int b,int c){
e[idx] = b , f[idx] = c ,ne[idx] = h[a] , h[a] = idx ++ ;
e[idx] = a , f[idx] = 0 ,ne[idx] = h[b] , h[b] = idx ++ ;
}
bool bfs(){ //找dep深度
int hh = 0 , tt = 0 ; //模拟队列
memset(st,0,sizeof st) ;
memset(dep,0x3f,sizeof dep) ;
q[0] = S , st[S] = 1 ,dep[S] = 0 ;
while(hh <= tt){
int t = q[hh++] ;
for(int i = h[t] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(!st[j] && f[i]){
st[j] = 1;
dep[j] = dep[t] + 1 ;
q[++tt] = j ;
}
}
}
if(dep[T] != INF ) return 1 ;
return 0 ;
}
int dfs(int u,int d){
if(u == T) return d ;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(f[i] && dep[j] == dep[u] + 1 ){
int nd ;
if(nd = dfs(j,min(d,f[i]))){
f[i] -= nd ;
f[i^1] += nd ;
return nd ;
}
}
}
return 0 ;
}
int dinic(){ // 最大流dinic算法
int res = 0 ;
while(bfs()){
int t ;
while(t = dfs(S,INF)) res += t ;
}
return res ;
}
int main(){
scanf("%d%d",&k,&n) ;
T = n + k + 1 ;
init() ;
for(int i = 1; i <= k ; i++){
scanf("%d",&cnt[i]) ;
sum += cnt[i] ;
}
for(int i = 1 ; i <= k ; i++)
if(cnt[i])
add(0,n + i,cnt[i]) ; //添加从源点到 题目类型的边
for(int i = 1 ; i <= n ; i++){
int p ;
scanf("%d",&p) ;
for(int j = 1 ; j <= p ; j++){
int x ;
scanf("%d",&x) ;
add(n + x ,i,1) ; //添加从类型到题目的边
}
}
int len = idx ;
for(int i = 1; i <= n ; i++) add(i,n+k+1,1) ; //添加从题目到汇点的边
int res = dinic() ;
if(res != sum) puts("No Solution!") ;
else{
for(int i = 0 ; i < len ; i++){
if(e[i] <= n && !f[i]){ //找到所有满足使用的边，记录
ans[e[i^1] - n].push_back(e[i]) ;
}
}
for(int i = 1; i <= k ; i ++){
printf("%d:",i) ;
for(int j = 0 ; j < ans[i].size() ; j ++ ){
printf(" %d",ans[i][j]) ;
}
puts("") ;
}
}
return 0;
}
3.P2774 方格取数问题
题目传送门洛谷 P2774 方格取数问题 — acwing 2183. 方格取数问题
题意是给一个矩阵选出方格，满足任意两个方格之间不能有公共边，使得选出方格数目最大。
可以把每个横坐标和纵坐标的和为奇数的和偶数的分成两类，可以看出，和是奇数的只会和和是偶数的点相邻。那么就是一个二分图了，需要找到其中的最大独立集，那么由二分图的最大独立集 = 总 - 最大匹配
由于匹配带边权，所以不使用网络流就需要跑ek，这里采取网络流，这里最大匹配可以看作最大流，。那么sum - 最大流就是结果了。
建图就采取了从和为奇数的边连向和为偶数的边。
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 110 , M = 5e4 + 100 , K = 1e4 + 1e3 ,INF = 0x3f3f3f3f ;
int n,m,S,T;
int a[N][N] ;
int h[K],e[M],f[M],ne[M],idx;
int q[K],dep[K];
bool st[K] ;
int sum ;
int dx[] = {1,0,-1,0} , dy[] = {0,1,0,-1} ;
int get_id(int x,int y){ //获得一个坐标的id
return x * m + y ;
}
void add(int a,int b,int c){ //加边
e[idx] = b,f[idx] = c,ne[idx] = h[a] ,h[a] = idx ++ ;
e[idx] = a,f[idx] = 0,ne[idx] = h[b] ,h[b] = idx ++ ;
}
bool bfs(){ //bfs找dep
int hh = 0 ,tt = 0 ;
memset(st,0,sizeof st) ;
memset(dep,0x3f,sizeof dep) ;
q[0] = 0 , dep[0] = 0 , st[0] = 1 ;
while(hh <= tt){
int t = q[hh++] ;
for(int i = h[t] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(!st[j] && f[i]){
dep[j] = dep[t] + 1 ;
st[j] = 1 ;
q[++tt] = j ;
}
}
}
if(dep[T] != INF) return 1 ;
return 0 ;
}
int dfs(int u,int d){
if(u == T) return d ;
for(int i = h[u] ;~ i ; i = ne[i]){
int j = e[i] ;
if(dep[j] == dep[u] + 1 && f[i]){
int nd ;
if(nd = dfs(j,min(d,f[i]))){
f[i] -= nd ;
f[i^1] += nd ;
return nd;
}
}
}
return 0;
}
int dinic(){ //最大流dinic
int res = 0 ;
while(bfs()){
int t ;
if(t = dfs(0,INF)) res += t ;
}
return res ;
}
int main(){
scanf("%d%d",&n,&m) ;
T = n * m + m + 1 ; //汇点
S = 0 ;
memset(h,-1,sizeof h) ;
for(int i = 1 ; i <= n ; i++){
for(int j = 1; j <= m ; j ++){
scanf("%d",&a[i][j]) ;
sum += a[i][j] ;
if((i + j) & 1){
add(0,get_id(i,j),a[i][j]) ; //源点到和为奇数的点，边权为奇数点的值
for(int k = 0 ; k < 4 ; k++){
int x = i + dx[k] , y = j + dy[k] ;
if(x <= 0 || y <= 0 || x > n || y > m) continue ;
add(get_id(i,j),get_id(x,y),INF) ; //和为奇数连到和为偶数
}
}
else add(get_id(i,j),T,a[i][j]) ; //和为偶数连到汇点
}
}
printf("%d\n",sum - dinic()) ;
return 0;
}
4.P3355 骑士共存问题
题目传送门洛谷 P3355 骑士共存问题 — acwing 2199. 骑士共存问题
这题和上一个题方格取数一样都是求最大独立集，建边方式类似，横纵坐标和是奇数的点为一个集合，其他的点为另一个集合。按照日字来建立边。答案就是sum - 最大流
- 最大流dinic算法
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 210 , M = 2e6 + 100 ,K = N * N , INF = 0x3f3f3f3f ;
int n,m,S,T ;
bool g[N][N] ;
int h[K],cur[M],e[M],f[M],ne[M],idx;
int q[K],dep[K] ;
bool st[K] ;
int res ;
int dx[] = {-1,-2,-2,-1,1,2,2,1} ;
int dy[] = {-2,-1,1,2,2,1,-1,-2} ;
int get_id(int x,int y){
return x * n + y ;
}
void add(int a,int b,int c){
e[idx] = b, f[idx] = c,ne[idx] = h[a] ,h[a] = idx ++ ;
e[idx] = a, f[idx] = 0,ne[idx] = h[b] ,h[b] = idx ++ ;
}
bool bfs(){
int hh = 0,tt = 0 ;
memset(st,0,sizeof st) ;
memset(dep,0x3f,sizeof dep) ;
memcpy(cur,h,sizeof h) ;
q[0] = 0 ,st[0] = 1 ,dep[0] = 0 ;
while(hh <= tt){
int t = q[hh++] ;
for(int i = h[t] ; ~ i ; i= ne[i]){
int j = e[i] ;
if(f[i] && !st[j]){
st[j] = 1 ;
dep[j] = dep[t] + 1 ;
q[++tt] = j ;
}
}
}
if(dep[T] != INF) return 1 ;
return 0 ;
}
int dfs(int u,int d){
if(u == T) return d;
for(int i = cur[u] ;~ i ; i = ne[i]){
cur[u] = i ;
int j = e[i];
if(f[i] && dep[j] == dep[u] + 1 ){
int nd ;
if(nd = dfs(j,min(d,f[i]))){
f[i] -= nd;
f[i^1] += nd ;
return nd;
}
}
}
return 0 ;
}
int dinic(){
int res = 0 ;
while(bfs()){
int t ;
while(t = dfs(0,INF)) res += t;
}
return res;
}
int main(){
scanf("%d%d",&n,&m) ;
memset(h,-1,sizeof h) ;
for(int i = 1; i <= m ; i++){
int a,b;
scanf("%d%d",&a,&b) ;
g[a][b] = 1 ;
}
S = 0 ,T = n * n + n + 1 ;
for(int i = 1; i <= n ; i++){
for(int j = 1; j <= n ; j++){
if(g[i][j]) continue ;
if((i + j) & 1 ){
for(int k = 0 ; k < 8 ; k++){
int x = i + dx[k] , y = j + dy[k] ;
if(g[x][y]) continue ;
if(x <= 0 || y <= 0 || x > n || y > n) continue ;
add(get_id(i,j),get_id(x,y),INF) ;
}
}
if((i + j) & 1) add(S,get_id(i,j),1) ;
else add(get_id(i,j),T,1) ;
}
}
printf("%d\n",n * n - m - dinic()) ;
return 0;
}
5.P4015 运输问题
题目传送门洛谷 P4015 运输问题 — acwing 2192. 运输问题
这道题就是最小费用流的板子题，可以将题目中边的流量设为1，来限制只能有一个，费用权值根据输入来设置，
这里有一个trick，题目中即让求最大费用流，右让求最小费用流，那么我们可以在跑完最小费用流后，重新建图，跑一遍将每个边费用置为原先相反数，再跑一遍最小费用流，那么答案就是结果的相反数。
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 210 , M = 3e4 + 100 , INF = 0x3f3f3f3f ;
int n,m,S,T;
int h[N],e[M],f[M],w[M],ne[M],idx;
int q[N],cost[N],dist[N],pre[N] ;
bool st[N] ;
int res,cnt ;
void add(int a,int b,int c,int d){ //加边函数
e[idx] = b,f[idx] = c,w[idx] = d,ne[idx] = h[a] ,h[a] = idx ++ ;
e[idx] = a,f[idx] = 0,w[idx] =-d,ne[idx] = h[b] ,h[b] = idx ++ ;
}
bool spfa(){ //最小费用流的spfa
int hh = 0 , tt = 1 ;
for(int i = 0 ; i <= T ; i ++){
st[i] = 0 ;
cost[i] = dist[i] = INF ;
pre[i] = -1 ;
}
q[0] = 0 ,st[0] = 1 ,cost[0] = 0 ;
while(hh != tt){
int t = q[hh++] ;
if(hh == N) hh = 0 ;
st[t] = 0 ;
for(int i = h[t] ;~ i ; i = ne[i]){
int j = e[i] ;
if(f[i] && cost[j] > cost[t] + w[i]){
cost[j] = cost[t] + w[i] ;
pre[j] = i ;
dist[j] = min(dist[t],f[i]) ;
if(!st[j]){
st[j] = 1;
q[tt++] = j ;
if(tt == N ) tt = 0 ;
}
}
}
}
if(cost[T] != INF) return 1 ;
return 0 ;
}
void dinic(){ //这里虽然写的是dinic，但是用的是ek算法，本来想写dinic名字就没改
res = cnt = 0 ;
while(spfa()){
res += dist[T] ;
for(int i = pre[T] ;~ i ; i = pre[e[i^1]]){
f[i] -= dist[T] ;
f[i^1] += dist[T] ;
}
cnt += dist[T] * cost[T] ;
}
}
int main(){
scanf("%d %d",&n,&m) ;
S = 0, T = n + m + 1 ;
memset(h,-1,sizeof h) ;
for(int i = 1 ; i <= n ; i++){
int x;
scanf("%d",&x) ;
add(0,i,x,0) ;
}
for(int i = 1; i <= m ; i ++){
int x;
scanf("%d",&x) ;
add(n + i,T,x,0) ;
}
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= m ; j++){
int x ;
scanf("%d",&x) ;
add(i,n+j,INF,x) ;
}
}
dinic() ;
printf("%d\n",cnt) ; //最小费用
for(int i = 0 ; i < idx ; i++){ //这里偷个懒
if(i&1){
f[i^1] += f[i] ; //直接把反向遍加到正向边上，反向边置为0
f[i] = 0 ;
w[i] = -w[i] ; //费用边权置为相反数
w[i^1] = -w[i^1] ;
}
}
dinic() ;
printf("%d\n",-cnt) ; //最大费用
return 0;
}
6.P2764 最小路径覆盖问题
题目传送门洛谷 P2764 最小路径覆盖问题 — acwing 2177. 最小路径覆盖问题
这题就是跑一遍最大流，关键就是找到路径，这里我采用并查集加新的边。
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 310 , M = 2e4 + 100 ,INF = 0x3f3f3f3f ;
int n,m,S,T;
int h[N],e[M],f[M],ne[M],idx;
int q[N],dep[N];
int p[N] ;
bool st[N] ;
void add(int a,int b,int c){ //最大流加边函数
e[idx] = b,f[idx] = c,ne[idx] = h[a] ,h[a] = idx ++ ;
e[idx] = a,f[idx] = 0,ne[idx] = h[b] ,h[b] = idx ++ ;
//cout << a<< " " << b << " " << c << "\n" ;
}
void add(int a,int b){ //求路径时的加边函数
e[idx] = b,ne[idx] = h[a],h[a] = idx ++ ;
}
int find(int x){ //并查集查找函数
if(x != p[x]) p[x] = find(p[x]) ;
return p[x] ;
}
bool bfs(){ //最大流的bfs找每个节点的dep深度
int hh = 0, tt = 0 ;
for(int i = 0 ; i <= T; i++){
dep[i] = INF ;
st[i] = 0 ;
}
q[S] = 0 ,dep[S] = 0 ,st[S] = 1 ;
while(hh <= tt){
int t = q[hh++] ;
for(int i = h[t] ;~ i ; i = ne[i]){
int j = e[i] ;
if(f[i] && !st[j]){
st[j] = 1;
dep[j] = dep[t] + 1 ;
q[++tt] = j ;
}
}
}
if(dep[T] != INF) return 1 ;
return 0 ;
}
int dfs(int u,int d){ //dinic的dfs
if(u == T) return d ;
int used = 0 ;
for(int i = h[u]; ~i ; i = ne[i]){
int j = e[i] ;
if(f[i] && dep[j] == dep[u] + 1 ){
int nd ;
if(nd = dfs(j,min(d-used,f[i]))){
f[i] -= nd;
f[i^1] += nd ;
used += nd ;
if(used == d) break ;
}
}
}
return used ;
}
void dfs2(int u){
printf("%d ",u) ;
st[u] = 1;
for(int i = h[u] ;~ i ; i = ne[i]){
int j = e[i] ;
if(!st[j]){
dfs2(j) ;
}
}
}
void dinic(){
while(bfs()){
dfs(0,INF) ;
}
}
int main(){
scanf("%d%d",&n,&m) ;
memset(h,-1,sizeof h) ;
S = 0 ,T = 2 * n + 1 ;
for(int i = 1 ; i <= m ; i++){
int a,b;
scanf("%d%d",&a,&b) ;
add(a,n + b,1) ;
}
int len = idx ;
for(int i = 1 ; i <= n; i++){
add(S,i,1) ;
add(i + n ,T ,1) ;
}
dinic() ;
idx = 0 ;
memset(h,-1,sizeof h) ;
memset(st,0,sizeof st) ;
for(int i = 1; i<= n ; i++) p[i] = i ; //并查集初始化
for(int i = 0 ; i < len ; i++){ //找到用了的边，然后加入到并查集
if((i & 1) && f[i]){ //将使用过的边进行重新建图
int a = e[i^1],b = e[i] ;
add(b,a-n) ;
int fa = find(a-n),fb = find(b) ;
p[fa] = fb ;
}
}
int cnt = 0 ;
for(int i = 1 ; i <= n ; i++){
if(p[i] == i){ //证明该点时是路径起点
cnt ++ ;
dfs2(i) ; //找到路径并输出
puts("") ;
}
}
printf("%d\n",cnt) ; //路径条数
return 0;
}
7.P2765 魔术球问题
题目传送门洛谷 P2765 魔术球问题 — acwing 2178. 魔术球问题
这道题可以贪心来做，就是每次要放数，依次从前往后找
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N = 110 ;
vector<int> v[N] ;
int main(){
int n ;
scanf("%d",&n) ;
int ans = 0;
for(int i = 1; ; i++){
bool flag = 0 ;
for(int j = 1 ;j <= n ; j++){
if(!v[j].size()){
v[j].push_back(i) ;
flag = 1 ;
break ;
}
else if( (int)sqrt(v[j].back() + i) * sqrt(v[j].back() + i) == v[j].back() + i){
v[j].push_back(i) ;
flag =1 ;
break ;
}
}
if(!flag) break ;
ans = i ;
}
printf("%d\n",ans) ;
for(int i = 1 ; i <= n ; i++){
for(int j : v[i]){
printf("%d ",j) ;
}
puts("") ;
}
return 0;
}
网络流的方法
于是我们引入一个叫“隐式图”的概念。
隐式图顾名思义，大白话来讲就是题目看着不像是图论，但是可以通过一些限制或关联进行建点，连边，最终通过图论的一些算法来求解。
参考 ： 隐式图题解 P2765 【网络流24题】魔术球问题
8.P3254 圆桌问题
题目传送门 洛谷 P3254 圆桌问题 — acwing 2179. 圆桌问题
这道题是给你了m个单位n个餐桌
接下来一行有m个数，每个数代表m个单位人数。在下一行是n个数，每个数代表餐桌能坐多少人。
要求每个餐桌上不能坐两个同一公司的人。
那么自然的可以想到可以将m个单位分别连向n个餐桌，容量设为1，那么从左边单位的集合到右边餐桌的集合的最大流，就是一个匹配，保证一个单位在一个餐桌上至多有一个人(因为容量设为1了)，求出的最大流如果等于所以公司总人数那么就是找到方案，否则就是没有找到方案。。将超级源点连接所以单位，将所有餐桌连接到超级汇点。
找到使用的边还是一样的思路，先记录编号，然后遍历，记录每个公司人数去那个餐桌
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 500 , M = 2e5 + 100 ,INF = 0x3f3f3f3f ;
int n,m,S,T ;
int h[N],e[M],f[M],ne[M],idx;
int q[N],dep[N];
bool st[N] ;
vector<int> ans[N] ;
void add(int a,int b,int c){ //最大流加边函数
e[idx] = b ,f[idx] = c ,ne[idx] = h[a] ,h[a] = idx ++ ;
e[idx] = a ,f[idx] = 0 ,ne[idx] = h[b] ,h[b] = idx ++ ;
}
bool bfs(){ //最大流找dep，
int hh = 0,tt = 0 ;
for(int i = 0; i <= T ; i++){
dep[i] = INF ;
st[i] = 0 ;
}
q[0] = 0 ,st[0] = 1,dep[0] = 0 ;
while(hh <= tt){
int t = q[hh++] ;
for(int i = h[t] ;~ i ; i = ne[i]){
int j = e[i];
if(!st[j] && f[i]){
dep[j] = dep[t] + 1;
st[j] = 1;
q[++tt] = j ;
}
}
}
if(dep[T] != INF) return 1;
return 0 ;
}
int dfs(int u,int d){ //dinic的dfs
if(u == T) return d ;
int used = 0 ;
for(int i = h[u] ;~ i ; i = ne[i]){
int j = e[i] ;
if(f[i] && dep[j] == dep[u] + 1 ){
int nd ;
if(nd = dfs(j,min(d - used,f[i]))){
f[i] -= nd ;
f[i^1] += nd ;
used += nd ;
if(used == d) break ;
}
}
}
return used ;
}
int dinic(){ //dinic
int res = 0 ;
while(bfs()){
res += dfs(0,INF) ;
}
return res ;
}
int main(){
scanf("%d%d",&n,&m) ;
memset(h,-1,sizeof h) ;
for(int i = 1; i <= n ; i++){
for(int j = 1 ; j <= m ; j++){
add(i,j+n,1) ;
}
}
int len = idx ;
S = 0 ,T = n + m + 1;
int sum = 0 ;
for(int i = 1; i <= n ; i++){
int x ;
scanf("%d",&x) ;
add(S,i,x) ;
sum += x;
}
for(int j = 1; j <= m ; j++){
int x;
scanf("%d",&x) ;
add(j + n ,T,x) ;
}
int res = dinic() ;
if(res == sum){
puts("1") ;
for(int i = 0 ; i < len ; i++){ //找到该单位人分别去那个餐桌
if( (i & 1) && f[i]){
int a = e[i^1] - n ,b = e[i] ;
ans[b].push_back(a) ;
}
}
for(int i = 1; i <= n; i ++){
for(int j : ans[i]){
printf("%d ",j) ;
}
puts("") ;
}
}
else{
puts("0") ;
}
return 0;
}
9.P4014 分配问题
题目传送门 洛谷 P4014 分配问题 — acwing 2193. 分配问题
题目就是一个简单的最小费用流和最大费用流
一样的思路，重新建图，将边的费用权值置为原先的相反数，再跑一遍最小费用流，然后就能得到最大费用流的相反数
刚开始写的时候，因为一个数组定义小了，wa了很多发。
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int N = 300 , M = 2e4 + 100 ,INF = 0x3f3f3f3f ;
int n,S,T ;
int h[N],e[M],w[M],f[M],ne[M],idx ;
int q[N],cost[N],cur[N] ;
bool st[N],vis[N];
int cnt ;
void add(int a,int b,int c,int d){ //最大流加边
e[idx] = b,f[idx] = c,w[idx] = d,ne[idx] = h[a] ,h[a] = idx ++ ;
e[idx] = a,f[idx] = 0,w[idx] =-d,ne[idx] = h[b] ,h[b] = idx ++ ;
}
bool spfa(){ //最小费用流的spfa
int hh = 0 , tt = 1 ;
for(int i = 0 ; i <= T ; i++){
st[i] = 0 ;
cost[i] = INF ;
cur[i] = h[i] ;
}
queue<int> qu ;
q[0] = 0 ,st[0] = 1 ,cost[0] = 0 ;
qu.push(S) ;
while(qu.size()){
int t = qu.front() ;
qu.pop() ;
st[t] = 0;
for(int i = h[t] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(f[i] && cost[j] > cost[t] + w[i]){
cost[j] = cost[t] + w[i];
if(!st[j]){
st[j] = 1 ;
qu.push(j) ;
}
}
}
}
if(cost[T] != INF) return 1 ;
return 0 ;
}
int dfs(int u,int d){ //最小费用流
if(u == T) {
vis[u] = 1 ;
return d ;
}
vis[u] = 1 ;
int used = 0 ;
for(int i = cur[u] ;~ i ; i = ne[i]){
cur[u] = i ;
int j = e[i] ;
if(!vis[j] && f[i] && cost[j] == cost[u] + w[i]){
int nd ;
if(nd = dfs(j,min(d-used,f[i]))){
f[i] -= nd ;
f[i^1] += nd ;
cnt += w[i] ;
used += d ;
if(used == d) break ;
}
}
}
return used;
}
int dinic(){
cnt = 0 ;
while(spfa()){
vis[T] = 1 ;
while(vis[T]){
memset(vis,0,sizeof vis) ;
dfs(0,INF) ;
}
// res += dist[T] ;
// for(int i = pre[T]; ~ i ; i = pre[e[i^1]]){
// f[i] -= dist[T] ;
// f[i^1] += dist[T] ;
// }
// cnt += cost[T] ;
}
return cnt;
}
int main(){
scanf("%d",&n) ;
S = 0 ,T = 2 * n + 1 ;
memset(h,-1,sizeof h) ;
for(int i = 1; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
int x;
scanf("%d",&x) ;
add(i,n+j,1,x) ;
}
}
for(int i =1 ;i <= n ; i++){
add(S,i,1,0) ;
add(i+n,T,1,0) ;
}
int res = dinic() ;
printf("%d\n",res) ;
for(int i = 0 ; i < idx ; i++){ //重新构建图
if(i & 1){
f[i^1] += f[i] ;
f[i] = 0 ;
w[i] = -w[i] ;
w[i^1] = -w[i^1] ;
}
}
res = dinic() ;
printf("%d\n",-res) ;
return 0;
}
10.P2761 软件补丁问题
题目传送门 洛谷 P2761 软件补丁问题 — acwing 2186. 软件补丁问题
这道题，读清楚题意，就明白每个补丁可以将一个状态，转化为另一个状态，那么，由于状态数不多(bug数最多是20个，所以 1 << 20 ,就可以表示，是1e6 级别)，可以使用状压，
然后可以跑最短路，就是从所有bug都在(1 << n) - 1, 二进制表示每一位1代表有一个bug，跑最短路，每次暴力枚举可以转化为那种状态，最总状态是0，无bug
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
const int N = 210 , M = 1e6 + 1e5 , INF = 0x3f3f3f3f ;
int n,m,S,T;
int q[M],dist[M],tm[N] ;
bool st[M] ;
string in[N],out[N] ;
bool check(int u,int state){ //检查state这个状态能否运行u这个补丁
for(int i = 0 ; i < n ; i++){
if(in[u][i] == '+'){
if((state >> i) & 1) ;
else return 0 ;
}
else if(in[u][i] == '-'){
if((state >> i )&1){
return 0 ;
}
}
}
return 1 ;
}
int change(int u,int state){ //返回state这个状态在u补丁后变为什么
for(int i = 0 ; i < n ; i++){
if(out[u][i] == '-'){
if((state >> i) & 1){
state ^= (1 << i) ;
}
}
else if(out[u][i] == '+'){
state |= (1 << i) ;
}
}
return state;
}
void spfa(){ //跑最短路
int hh = 0 ,tt = 1 ; //数组模拟循环队列
memset(dist,0x3f,sizeof dist) ;
memset(st,0,sizeof st) ;
q[0] = S , st[S] = 1, dist[S] = 0 ;
while(hh <= tt){
int t = q[hh++] ;
if(hh == M) hh = 0;
st[t] = 0 ;
for(int i = 1 ; i <= m ; i++){ //暴力枚举m个补丁
if(check(i,t)){
int j = change(i,t) ;
if(dist[j] > dist[t] + tm[i]){
dist[j] = dist[t] + tm[i] ;
if(!st[j]){
st[j] = 1 ;
q[tt++] = j ;
if(tt == M) tt = 0 ;
}
}
}
}
}
if(dist[0] == INF) cout << "0\n" ;
else cout << dist[0] << "\n" ;
}
int main(){
cin >> n >> m ;
S = (1 << n) - 1 ,T = 0 ;
for(int i = 1 ;i <= m ; i++){
cin >> tm[i] >> in[i] >> out[i] ; //读入每个状态变化
}
spfa() ; //跑最短路
return 0;
}
11.P4013 数字梯形问题
题目传送门 洛谷 P4013 数字梯形问题 — acwing 2191. 数字梯形问题
这道题，考察建图，然后跑最大费用流
第一个，需要从梯形的顶至底的 m 条路径互不相交。那么可以拆点，将每个点的边费用加到拆点之间，并将容量设为1，那么就可以保证跑出来每个点只用一次
第二个，从梯形的顶至底的 m 条路径仅在数字结点处相交。，超级源点连接第一行，将每个点的权值附在指向第一行点的边上，那么就是所有的边容量是1，将每个点的值加到指向他的边上
注意由于在最后一行可以同时到一个点，所有最后一行的点连接到超级汇点的容量是INF
第三个 ，规则 3：从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。那么可以将第二个修改为除了从原点出来的边容量是1（为了限制共有最大流是m，就是m条路径），其他的边的容量可以设置为INF
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 2e4 + 100 , M = 2e5 + 100 ,K = 100 ,INF = 0x3f3f3f3f ;
int n,m,S,T ;
int h[N],e[M],w[M],f[M],ne[M],idx;
int q[N],cost[N] ;
bool st[N],vis[N] ;
int a[K][K] ;
int cnt ;
void init(){
idx = 0 ;
memset(h,-1,sizeof h) ;
}
void add(int a,int b,int c,int d){
e[idx] = b,f[idx] = c,w[idx] = d,ne[idx] = h[a] , h[a] = idx ++ ;
e[idx] = a,f[idx] = 0,w[idx] =-d,ne[idx] = h[b] , h[b] = idx ++ ;
//cout << a << " " <<b << " " <<c << " " << d << "\n" ;
}
int get_id(int i,int j){ //获得id
return i * (n + m - 1) + j ;
}
bool spfa(){
int hh = 0 ,tt = 1 ;
for(int i = 0 ; i <= T ; i ++){
st[i] = 0 ;
cost[i] = INF ;
}
q[0] = 0 ,st[0] = 1 ,cost[0] = 0 ;
while(hh != tt){
int t = q[hh++] ;
if(hh == N) hh = 0 ;
st[t] = 0 ;
for(int i = h[t] ;~ i ; i = ne[i]){
int j = e[i] ;
if(f[i] && cost[j] > cost[t] + w[i]){
cost[j] = cost[t] + w[i] ;
if(!st[j]){
st[j] = 1;
q[tt++] = j ;
if(tt == N ) tt = 0 ;
}
}
}
}
if(cost[T] != INF) return 1 ;
return 0 ;
}
int dfs(int u,int d){
vis[u] = 1;
if(u == T) return d;
int used = 0 ;
for(int i = h[u] ;~ i ; i = ne[i]){
int j = e[i] ;
if(!vis[j] && f[i] && cost[j] == cost[u] + w[i]){
int nd;
if(nd = dfs(j,min(d-used,f[i]))){
f[i] -= nd ;
f[i^1] += nd ;
used += nd ;
cnt += w[i] ;
if(used == d) break ;
}
}
}
return used ;
}
void dinic(){ //dinic跑最小费用流
int res = 0 ;
cnt = 0 ;
while(spfa()){
vis[T] = 1 ;
while(vis[T]){
memset(vis,0,sizeof vis) ;
res += dfs(0,INF) ;
}
}
}
void slove1(){ //拆点
init() ;
S = 0 , T = 2 * (n + 1) * (n + m - 1) + 1 ;
int len = (n + 1) * (n + m - 1) ;
for(int i = 1; i < n ; i++){
for(int j = 1 ; j <= m + i - 1 ; j++){
add(get_id(i,j) + len,get_id(i+1,j),1,0) ;
add(get_id(i,j) + len,get_id(i+1,j+1),1,0) ;
}
}
for(int i = 1 ; i <= m ;i++) add(S,get_id(1,i),1,0) ;
for(int j = 1 ; j <= m + n - 1 ; j ++) add(get_id(n,j) + len,T,1,0) ;
for(int i = 1 ; i <= n ;i++){
for(int j = 1 ; j <= m + i - 1 ; j ++){
add(get_id(i,j),get_id(i,j) + len,1,-a[i][j]) ; //将所有点的值加到拆点之间的边上，容量是1，那么每个点只会用一次
}
}
dinic() ;
printf("%d\n",-cnt) ;
}
void slove2(){
init() ;
S = 0 , T = (n + 1) * (n + m - 1) + 1 ;
for(int i = 1; i < n ; i++){
for(int j = 1 ; j <= m + i - 1 ; j++){
add(get_id(i,j),get_id(i+1,j),1,-a[i+1][j]) ;
add(get_id(i,j) ,get_id(i+1,j+1),1,-a[i+1][j+1]) ;
}
}
for(int i = 1 ; i <= m ;i++) add(S,get_id(1,i),1,-a[1][i]) ;
for(int j = 1 ; j <= m + n - 1 ; j ++) add(get_id(n,j) ,T,INF,0) ; //注意最后容量是INF，因为可以共用最后一行的节点
dinic() ;
printf("%d\n",-cnt) ;
}
void slove3(){
init() ;
S = 0 , T = (n + 1) * (n + m - 1) + 1 ;
for(int i = 1; i < n ; i++){
for(int j = 1 ; j <= m + i - 1 ; j++){
add(get_id(i,j),get_id(i+1,j),INF,-a[i+1][j]) ;
add(get_id(i,j),get_id(i+1,j+1),INF,-a[i+1][j+1]) ;
}
}
for(int i = 1 ; i <= m ;i++) add(S,get_id(1,i),1,-a[1][i]) ; //只有从源点出来的，容量是1，限制为m条路
for(int j = 1 ; j <= m + n - 1 ; j ++) add(get_id(n,j),T,INF,0) ;
dinic() ;
printf("%d\n",-cnt) ;
}
int main(){
scanf("%d%d",&m,&n) ;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= m + i - 1 ; j ++){
scanf("%d",&a[i][j]) ;
}
}
slove1() ; //分别解决1，2，3
slove2() ;
slove3() ;
return 0;
}
12.P4016 负载平衡问题
题目传送门 洛谷 P4016 负载平衡问题 — acwing 2194. 负载平衡问题
G 公司有 nn 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 nn 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。
这个题目可以贪心来做，参考 ： P4016 负载平衡问题 题解
来说一下网络流做法，由于是找到一个最小搬运量，其实就是隐含跑一个最小费用流，把搬运看作花费。
那么怎么建图，由于知道最终都是相同的，可以先计算出平均值，那么可以从超级源点连向每个点，容量为初始值（每个点初始货物），接下来连接每个点到超级汇点，容量为平均值，，最后由于每个点可以向两边搬运，所有将每个点连接向两边。注意是一个环形的注意处理1和n
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 2e4 , M = 2e4 + 100 ,INF = 0x3f3f3f3f ;
int n,m,S,T ;
int h[N],e[M],f[M],w[M],ne[M],idx;
int q[N],cost[N],dist[N],pre[N] ;
bool st[N] ;
int a[N] ,sum ;
void add(int a,int b,int c,int d){ //加边
e[idx] = b ,f[idx] = c,w[idx] = d ,ne[idx] = h[a] ,h[a] = idx ++ ;
e[idx] = a ,f[idx] = 0,w[idx] =-d ,ne[idx] = h[b] ,h[b] = idx ++ ;
}
bool spfa(){ //最小费用流spfa
int hh = 0 , tt = 1 ;
for(int i = 0 ; i <= T ; i ++){
st[i] = 0 ;
dist[i] = cost[i] = INF ;
pre[i] = -1 ;
}
q[0] = 0, st[0] = 1 ,cost[0] = 0 ;
while(hh <= tt){
int t = q[hh++] ;
if(hh == N) hh = 0 ;
st[t] = 0 ;
for(int i = h[t] ;~ i; i = ne[i]){
int j = e[i] ;
if(f[i] && cost[j] > cost[t] + w[i]){
cost[j] = cost[t] + w[i] ;
pre[j] = i ;
dist[j] = min(dist[t],f[i]) ;
if(!st[j]){
st[j] = 1;
q[tt++] = j ;
if(tt == N) tt = 0 ;
}
}
}
}
if(cost[T] != INF) return 1 ;
return 0 ;
}
int dinic(){ //这是最小费用流的ek写法（有dfs就是dinic没有就是ek，有时候本来想写dinic所以函数名是dinic，但代码是ek）
int res ,cnt ;
res = cnt = 0 ;
while(spfa()){
res += dist[T] ;
for(int i = pre[T] ; ~ i; i = pre[e[i^1]]){
f[i] -= dist[T] ;
f[i^1] += dist[T] ;
}
cnt += cost[T] * dist[T] ;
}
return cnt ;
}
int main(){
scanf("%d",&n) ;
S = 0 , T = n + 1 ;
memset(h,-1,sizeof h) ;
for(int i = 1; i <= n ; i++){
scanf("%d",&a[i]);
sum += a[i] ;
}
int avg = sum / n ;
for(int i = 1; i <= n ; i++){ //将每个点汇点相连，将超级源点连向每个点
add(S,i,a[i],0) ;
add(i,T,avg,0) ;
}
for(int i = 1; i <= n; i ++){ //连接相邻的边
if( i == 1) add(i,n,INF,1) ;
else add(i,i-1,INF,1) ;
if( i == n) add(i,1,INF,1) ;
else add(i,i+1,INF,1) ;
}
int res = dinic() ;
printf("%d\n",res) ;
return 0;
}
13.P2770 航空路线问题
题目传送门 P2770 航空路线问题— acwing2185. 航空路线问题
这道题，就是找到一条路径从第一个点到终点，再从终点回到第一个点，除了第一个起点外每个点只能经过一次，找到经过最多的城市路径。
由于需要找到经过城市最多，就是一个最大费用流问题，可以通过最大流是2来保证从起点到终点有两个路，然后费用是最大城市数量，
拆点就是将一个点拆为流入该点的一个点，和从该点输出的一个点，这样可以在流入点和输出点直间加边来满足一些限制
那么可以拆点，将每个城市拆为两个点，那么从源点连向起点时容量为2，从终点连到汇点时容量是2，从起点连向起点的输出点容量是2，从终点到终点的输出点容量是2，其他边容量都是1
那么有两个特殊情况。最大流是不是2，当最大流是1且有一条1~n的边，就是从起点可以直接到终点且最大流只有1，那么输出2个城市，输出起点，终点，起点，否则输出无解
最大流是2，找到两个路径输出即可。
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
const int N = 210 , M = 4e4 + 100 ,INF = 0x3f3f3f3f ;
int n,m,S,T,g_id;
int h[N],e[M],f[M],w[M],ne[M],idx ;
int q[N],cost[N] ;
bool st[N],vis[N] ;
map<string,int> g ;
map<int,string> fg ;
vector<string> path1,path2;
int cnt;
void add(int a,int b,int c,int d){ //跑费用流的加边函数
e[idx] = b,f[idx] = c,w[idx] = d, ne[idx] = h[a] ,h[a] = idx ++ ;
e[idx] = a,f[idx] = 0,w[idx] =-d, ne[idx] = h[b] ,h[b] = idx ++ ;
//cout << a << " " << b << " " << c << " " << d << "\n" ;
}
void add(int a,int b){ //找路径的加边函数
e[idx] = b ,ne[idx] = h[a] ,h[a] = idx ++ ;
}
bool spfa(){
int hh = 0 ,tt = 1 ;
for(int i = 0 ; i <= T ; i++){
st[i] = 0 ;
cost[i] = INF ;
}
q[S] = 0 ,st[S] = 1 ,cost[S] = 0 ;
while(hh != tt){
int t = q[hh++] ;
if(hh == N) hh = 0 ;
st[t] = 0 ;
for(int i = h[t] ;~i ; i = ne[i]){
int j = e[i] ;
if(f[i] && cost[j] > cost[t] + w[i]){
cost[j] = cost[t] + w[i] ;
if(!st[j]){
st[j] = 1 ;
q[tt++] = j ;
if(tt == N) tt = 0 ;
}
}
}
}
if(cost[T] != INF) return 1 ;
return 0 ;
}
int dfs(int u,int d){ //最小费用流的dfs
vis[u] = 1 ;
if(u == T ) return d ;
int used = 0 ;
for(int i = h[u] ; ~i ; i = ne[i]){
int j = e[i] ;
if(!vis[j] && f[i] && cost[j] == cost[u] + w[i]){
int nd;
if(nd = dfs(j,min(d-used,f[i]))){
f[i] -= nd ;
f[i^1] += nd;
used += nd ;
cnt += w[i];
if(used == nd) break ;
}
}
}
return used ;
}
int dinic(){ //dinic实现最小费用流
int res = 0 ;
while(spfa()){
vis[T] = 1 ;
while(vis[T]){
memset(vis,0,sizeof vis) ;
res += dfs(S,INF) ;
}
}
return res ;
}
void dfs1(int u,vector<string> &path){ //找路径，一个普通的dfs
path.push_back(fg[u]) ;
vis[u] = 1;
for(int i = h[u] ;~ i ; i = ne[i]){
int j = e[i] ;
if(vis[j]) continue ;
dfs1(j,path) ;
break ;
}
}
int main(){
cin >> n >> m ;
memset(h,-1,sizeof h) ;
S = 0 , T = 2 * n + 1 ;
for(int i = 1 ; i <= n ; i ++){
string x ;
cin >> x ;
if(!g.count(x)){
g[x] = ++ g_id ; //使用map来映射字符串到数
fg[g_id] = x ; //将数映射到字符串
}
if(i == 1) add(S,g[x],2,0) ;
if(i == n ) add(g[x]+n,T,2,0) ;
if(i == 1 || i == n){
add(i,i+n,2,-1) ;
}
else add(i,i+n,1,-1) ;
}
int len = idx ;
bool flag = 0 ;
for(int i = 1 ; i <= m ;i ++){
string a,b;
cin >> a >> b ;
add(g[a]+n,g[b],1,0) ;
if(g[a] == 1 && g[b] == n) flag = 1;
}
int len2 = idx ;
int res = dinic() ;
if(res == 1 && flag ){ //特殊情况1，最大流是1，含有1~n这条边，证明可以从1~n然后从n到1
cout << "2\n" ;
cout << fg[1] << "\n" << fg[n] << "\n" << fg[1] << "\n" ;
return 0 ;
}
if(res != 2) { //最大流不是2，无解
cout << "No Solution!\n" ;
return 0 ;
}
else printf("%d\n",-cnt - 2) ; //由于找最大费用流的时候，起点和终点都算了两次，所有最后-cnt需要-2
idx = 0 ;
memset(h,-1,sizeof h) ;
for(int i = len ; i < len2; i ++){ //建边，看那些边使用了，为找路径准备
if(i&1 && f[i]){
int a = e[i] - n,b = e[i^1] ;
add(a,b) ;
}
}
memset(vis,0,sizeof vis) ;
dfs1(1,path1) ; //找路径
dfs1(1,path2) ;
reverse(path2.begin(),path2.end()) ; //由于是正着找路径的，所有最后反转一下
for(auto j : path1){
cout<< j <<"\n" ;
}
for(auto j : path2){
cout << j << "\n";
}
return 0;
}
待更新~~
很多题根本没必要放代码，即使放也不用全放，像网络流的板子不用一遍又一遍的重复吧，这样会让阅读体验极差
收到，之后会加一个目录(可以直接跳转到页面的题目位置)，或者把代码贴在pastebin，直接放链接。（
还没学会网上的如何生成markdown跳转目录）