什么网站做电气自动化兼职,潍坊住房和城乡建设厅网站,泰州哪家网做网站,广东深圳广东深圳网站建设文章目录信息汇总表格飞行员配对方案问题分配问题运输问题数字梯形问题最小路径覆盖问题魔术球问题圆桌问题试题库问题深海机器人问题航空路线问题火星探险问题太空飞行计划问题方格取数问题骑士共存问题最长不下降子序列问题孤岛营救问题汽车加油行驶问题[CTSC1999]家园 / 星际…
文章目录信息汇总表格飞行员配对方案问题分配问题运输问题数字梯形问题最小路径覆盖问题魔术球问题圆桌问题试题库问题深海机器人问题航空路线问题火星探险问题太空飞行计划问题方格取数问题骑士共存问题最长不下降子序列问题孤岛营救问题汽车加油行驶问题[CTSC1999]家园 / 星际转移问题餐巾计划问题最长k可重区间集问题最长k可重线段集问题负载平衡问题软件补丁问题总结小结Ⅰ小结Ⅱ小结Ⅰ、Ⅱ 补充小结Ⅲ网络流经典模型网格图的行列匹配(Upd2022-02-15)图的入度出度匹配(Upd2022-02-15)连续区间建图问题信息汇总表格
题目考察知识点飞行员配对方案问题最大匹配最大流分配问题最大完备匹配最大/最小费用流运输问题多重匹配最大/最小费用流小结Ⅰ数字梯形问题//最小路径覆盖问题魔术球问题解的存在性残余网络上继续求解圆桌问题最大流试题库问题深海机器人问题特殊边权/点权拆点航空路线问题火星探险问题小结Ⅱ太空飞行计划问题最大权闭合子图方格取数问题限制绑定及输出方案骑士共存问题最大流小结Ⅰ、Ⅱ补充最长不下降子序列问题特殊建图建分层图孤岛营救问题汽车加油行驶问题[CTSC1999]家园 / 星际转移问题餐巾计划问题小结Ⅲ最长k可重区间集问题特殊建图一流对多流最长k可重线段集问题负载平衡问题//软件补丁问题
飞行员配对方案问题
luogu-P2756
左部 mmm 个点表示外籍飞行员右部 n−mn-mn−m 个点表示英国飞行员二者能好好配合就连一条流量为无穷111也可以的边。
源点向左部点连边右部点向汇点连边流量 111表示该点只能被选择一次。答案即源点到汇点的最大流。
如果一条左右部边被流意味着该边连接的两个人是一个配对。
绝对不能建成左右部点流量为 111 而与源/汇点流量无穷二者同时存在因为这样就不能限制每个点只能选一次这种建图是限制每种关系只能选一次。
#include bits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 105
struct node { int to, nxt, flow; }E[maxn * maxn];
int head[maxn], cur[maxn], dep[maxn];
int n, m, cnt -1, s, t;
queue int q;void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w };head[u] cnt;E[ cnt] { u, head[v], 0 };head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( ! cap or u t ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d, m, n );int u, v;while( scanf( %d %d, u, v ) ) {if( ! ~ u and ! ~ v ) break;addedge( u, v, inf );}s 0, t n 1;for( int i 1;i m;i ) addedge( s, i, 1 );for( int i m 1;i n;i ) addedge( i, t, 1 );int ans 0;while( bfs() ) ans dfs( s, inf );printf( %d\n, ans );for( int i 1;i m;i ) {for( int j head[i];~ j;j E[j].nxt )if( E[j].to i and E[j ^ 1].flow ) { printf( %d %d\n, i, E[j].to ); break; }}return 0;
}分配问题
luogu-P4014
建图同上一题只不过左部点到右部点的边还要带个边权表示选择这对工作关系的“花费”。
选择的人和工件是不带来”花费“的只有工作关系带来“花费”。
最大费用流将最小费用流 SPFA\text{SPFA}SPFA 的松弛符号或“花费”变号即可。
#include bits/stdc.h
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define maxn 205
#define maxm 50000
int n, cnt, s, t;
bool vis[maxn];
int lst[maxn], dis[maxn], head[maxn];
int c[maxn][maxn];
struct node { int to, nxt, flow, cost; }E[maxm];
queue int q;void addedge( int u, int v, int flow, int cost ) {E[ cnt] { v, head[u], flow, cost }; head[u] cnt;E[ cnt] { u, head[v], 0, -cost }; head[v] cnt;
}bool SPFA() {memset( lst, -1, sizeof( lst ) );memset( dis, 0x3f, sizeof( dis ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to; if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}int MCMF() {int cost 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i].flow - flow;E[i ^ 1].flow flow;cost E[i].cost * flow;}}return cost;
}signed main() {scanf( %lld, n );for( int i 1;i n;i )for( int j 1;j n;j )scanf( %lld, c[i][j] );s 0, t n 1 | 1;cnt -1, memset( head, -1, sizeof( head ) );for( int i 1;i n;i ) {addedge( s, i, 1, 0 );addedge( i n, t, 1, 0 );}for( int i 1;i n;i )for( int j 1;j n;j )addedge( i, j n, inf, c[i][j] );printf( %lld\n, MCMF() );cnt -1, memset( head, -1, sizeof( head ) );for( int i 1;i n;i ) {addedge( s, i, 1, 0 );addedge( i n, t, 1, 0 );}for( int i 1;i n;i )for( int j 1;j n;j )addedge( i, j n, inf, -c[i][j] );printf( %lld\n, - MCMF() );return 0;
}运输问题
luogu-P4015
建图大致同上一题只不过这次的流量限制不再为 111。仓库和货物的各自限制不同。
#include bits/stdc.h
using namespace std;
#define maxn 205
#define maxm 30000
#define int long long
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow, cost; }E[maxm];
queue int q;
int m, n, s, t, cnt;
bool vis[maxn];
int head[maxn], lst[maxn], dis[maxn];
int a[maxn], b[maxn], c[maxn][maxn];void addedge( int u, int v, int flow, int cost ) {E[ cnt] { v, head[u], flow, cost }; head[u] cnt;E[ cnt] { u, head[v], 0, -cost }; head[v] cnt;
}bool SPFA() {memset( dis, 0x3f, sizeof( dis ) );memset( lst, -1, sizeof( lst ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}int MCMF() {int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i].flow - flow;E[i ^ 1].flow flow;ans flow * E[i].cost;}}return ans;
}signed main() {scanf( %lld %lld, m, n );s 0, t n m 1;for( int i 1;i m;i ) scanf( %lld, a[i] );for( int i 1;i n;i ) scanf( %lld, b[i] );for( int i 1;i m;i )for( int j 1;j n;j )scanf( %lld, c[i][j] );cnt -1, memset( head, -1, sizeof( head ) );for( int i 1;i m;i ) addedge( s, i, a[i], 0 );for( int i 1;i n;i ) addedge( i m, t, b[i], 0 );for( int i 1;i m;i )for( int j 1;j n;j )addedge( i, j m, inf, c[i][j] );printf( %lld\n, MCMF() );cnt -1, memset( head, -1, sizeof( head ) );for( int i 1;i m;i ) addedge( s, i, a[i], 0 );for( int i 1;i n;i ) addedge( i m, t, b[i], 0 );for( int i 1;i m;i )for( int j 1;j n;j )addedge( i, j m, inf, -c[i][j] );printf( %lld\n, -MCMF() );return 0;
}小结Ⅰ。
数字梯形问题
luogu-P4013
这道题就能体现小结的所求问题不同建边方式不同。你可以检查一下自己是否真的都明白了
路径不交即限制每个点只能走一次。
路径仅在结点处相交即限制每条边只能走一次。
路径可交即每条边无限制。
#include bits/stdc.h
using namespace std;
#define maxn 2000
#define maxm 50000
#define int long long
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow, cost; }E[maxm];
int lst[maxn], dis[maxn], head[maxn], a[maxn];
int id[maxn][maxn];
bool vis[maxn];
int n, m, cnt, s, t;
queue int q;void addedge( int u, int v, int w, int c ) {E[ cnt] { v, head[u], w, c }, head[u] cnt;E[ cnt] { u, head[v], 0, -c }, head[v] cnt;
}bool SPFA() {memset( lst, -1, sizeof( lst ) );memset( dis, 0x3f, sizeof( dis ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}int MCMF() {int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i].flow - flow;E[i ^ 1].flow flow;ans E[i].cost * flow;}}return ans;
}signed main() {scanf( %lld %lld, m, n );int num 0;for( int i 1;i n;i )for( int j 1;j m i;j )id[i][j] num, scanf( %lld, a[num] );//case 1memset( head, -1, sizeof( head ) );s 0, t num 1 | 1, cnt -1;for( int i 1;i m;i ) addedge( s, id[1][i], 1, 0 );for( int i 1;i n;i )for( int j 1;j m i;j ) {addedge( id[i][j], id[i][j] num, 1, -a[id[i][j]] );addedge( id[i][j] num, id[i 1][j], inf, 0 );addedge( id[i][j] num, id[i 1][j 1], inf, 0 );}for( int i 1;i m n;i ) addedge( id[n][i], t, 1, -a[id[n][i]] );printf( %lld\n, -MCMF() );//case 2memset( head, -1, sizeof( head ) );s 0, t num 1, cnt -1;for( int i 1;i m;i ) addedge( s, id[1][i], 1, 0 );for( int i 1;i n;i )for( int j 1;j m i;j ) {addedge( id[i][j], id[i 1][j], 1, -a[id[i][j]] );addedge( id[i][j], id[i 1][j 1], 1, -a[id[i][j]] );}for( int i 1;i m n;i )addedge( id[n][i], t, inf, -a[id[n][i]] );printf( %lld\n, -MCMF() );//case 3memset( head, -1, sizeof( head ) );s 0, t num 1, cnt -1;for( int i 1;i m;i ) addedge( s, id[1][i], 1, 0 );for( int i 1;i n;i )for( int j 1;j m i;j ) {addedge( id[i][j], id[i 1][j], inf, -a[id[i][j]] );addedge( id[i][j], id[i 1][j 1], inf, -a[id[i][j]] );}for( int i 1;i m n;i )addedge( id[n][i], t, inf, -a[id[n][i]] );printf( %lld\n, -MCMF() );return 0;
}最小路径覆盖问题
luogu-P2764
限制每个点只能用一次且必用。输出方案。
枚举左部点以及枚举单位与右部点的连边。可以通过反向边是否为 111 判断是否流了这条边。
注意左部点还与源点有连边所以需要判断这条边另一端不是源点。
并将右部点对应原图上的点入度 111从原图上入度为 000 的点开始搜索路径输出即可。
#include bits/stdc.h
using namespace std;
#define maxn 500
#define maxm 20000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow; } E[maxm];
int dep[maxn], cur[maxn], head[maxn], vis[maxn], deg[maxn];
int n, m, cnt -1, s, t;
queue int q;void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w }; head[u] cnt;E[ cnt] { u, head[v], 0 }; head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( E[i].flow, cap ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}void dfs( int u ) {if( ! u ) return;printf( %d , u );dfs( vis[u] );
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d, n, m );s 0, t n 1 | 1;for( int i 1, u, v;i m;i ) {scanf( %d %d, u, v );addedge( u, v n, inf );}for( int i 1;i n;i ) {addedge( s, i, 1 );addedge( i n, t, 1 );}int ans 0;while( bfs() ) ans dfs( s, inf );for( int i 1;i n;i )for( int j head[i];~ j;j E[j].nxt )if( E[j].to i and E[j ^ 1].flow ) {vis[i] E[j].to - n; deg[E[j].to - n];}for( int i 1;i n;i )if( ! deg[i] ) dfs( i ), puts();printf( %d\n, n - ans );return 0;
}魔术球问题
luogu-P2765
所有的操作都是关于珠子的编号的。以每一个珠子为点若满足条件编号相加为平方数就两两连边。
题目转化成图的问题就是 “对于给定的 n计算不超过 n 条路径最多可以覆盖多少满足条件的节点”。
最小边覆盖 点总数 −-− 最大匹配。
有这么个性质于是再将此图进行拆点转化成二分图的形式每加一个点就在上面跑网络流并统计总匹配如果发现 点总数 −-− 最大匹配 最小边覆盖 那就退出。
我们每次重新跑网络流时都是在跑残量网络即我们每次所得的最大流都是增加的匹配数所以是累加得到总的匹配数。
#include bits/stdc.h
using namespace std;
#define maxn 10000
#define maxm 400000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow; }E[maxm];
int n, s, t, cnt -1;
int dep[maxn], cur[maxn], head[maxn], p[maxn];
queue int q;void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w }, head[u] cnt;E[ cnt] { u, head[v], 0 }, head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( ! cap or u t ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {int v E[i].to; cur[u] i;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, inf );return ans;
}void print( int u ) {for( int i head[u];~ i;i E[i].nxt ) {if( E[i].to s or E[i].to t or E[i].flow ) continue;else printf( %d , E[i].to 1 );print( ( E[i].to 1 ) 1 );}
}int main() {memset( head, -1, sizeof( head ) );scanf( %d, n );int tot 0, x 0; s 0, t 1;while( tot n ) { x;addedge( s, x 1, 1 );addedge( x 1 | 1, t, 1 );for( int i sqrt( x ) 1;i * i ( x 1 );i )addedge( ( i * i - x ) 1, x 1 | 1, 1 );if( ! dinic() ) p[ tot] x;}printf( %d\n, -- x );for( int i 1;i n;i ) {printf( %d , p[i] );print( p[i] 1 );puts();}return 0;
}圆桌问题
luogu-P3254
从同一个单位来的代表不在同一个餐桌就餐等价于限制同样的单位和餐桌的配对只能有 111 次。
建图不再赘述这里主要是要输出就餐的方案。
一条单位和餐桌连边被流就意味着该单位有一个人在这个餐桌就餐。
枚举单位左部点以及枚举单位与餐桌右部点的连边。可以通过反向边是否为 111 判断是否流了这条边。
注意左部点还与源点有连边所以需要判断这条边另一端不是源点。
#include bits/stdc.h
using namespace std;
#define maxn 500
#define maxm 100000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow; }E[maxm];
int m, n, s, t, cnt -1;
int dep[maxn], cur[maxn], head[maxn];
queue int q;void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w }, head[u] cnt;E[ cnt] { u, head[v], 0 }, head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( ! cap or u t ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {int v E[i].to; cur[u] i;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d, m, n );s 0, t n m 1; int ans 0;for( int i 1, x;i m;i ) {scanf( %d, x );addedge( s, i, x );ans x;}for( int i 1, x;i n;i ) {scanf( %d, x );addedge( i m, t, x );}for( int i 1;i m;i ) for( int j 1;j n;j )addedge( i, j m, 1 );while( bfs() ) ans - dfs( s, inf );if( ans ) return ! printf( 0\n );else printf( 1\n );for( int i 1;i m;i ) {for( int j head[i];~ j;j E[j].nxt )if( E[j].to i and E[j ^ 1].flow ) printf( %d , E[j].to - m );puts();}return 0;
}试题库问题
luogu-P2763
完全同上。
#include bits/stdc.h
using namespace std;
#define maxn 2000
#define maxm 50000
#define inf 0x3f3f3f3f
int k, n, s, t, cnt -1;
int dep[maxn], cur[maxn], head[maxn];
struct node { int to, nxt, flow; }E[maxm];
queue int q;void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w }; head[u] cnt;E[ cnt] { u, head[v], 0 }; head[v] cnt;
}bool bfs() {memcpy( cur, head, sizeof( head ) );memset( dep, 0, sizeof( dep ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( E[i].flow, cap ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d, k, n );s 0, t n k 1; int ans 0;for( int i 1;i n;i ) addedge( s, i, 1 );for( int i 1, x;i k;i ) {scanf( %d, x );addedge( i n, t, x );ans x;}for( int i 1, num;i n;i ) {scanf( %d, num );for( int j 1, x;j num;j ) {scanf( %d, x );addedge( i, x n, 1 );}}while( bfs() ) ans - dfs( s, inf );if( ans ) return ! printf( No Solution!\n );for( int i 1;i k;i ) {printf( %d:, i );for( int j head[i n];~ j;j E[j].nxt )if( E[j].to i n and E[j].flow ) printf( %d, E[j].to );puts();}return 0;
}深海机器人问题
luogu-P4012
将机器人抽象成流量从源点向 (0,0)(0,0)(0,0) 的流量设置为机器人个数。
原图上的边在新图上全都存在。
一条边流过多少流量就意味着有多少个机器人走了这条边。
本题特殊的是一条边只贡献一次边权多个机器人多次走过也只计算一次。
换言之重要的是第一次经过这一次才会带来这条边权“花费”。
怎么在图上体现—— “拆出来“。
即一条边连两次一条流量为 111 带”花费“代表第一次经过一条流量无穷不带花费代表第 n(n1)n(n1)n(n1) 次经过。
跑最小费用流的时候就会先跑边权为负的即先跑代表第一次的边。
#include bits/stdc.h
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define maxn 800
#define maxm 1000000
struct node { int to, nxt, flow, cost; }E[maxm];
int dis[maxn], lst[maxn], head[maxn];
bool vis[maxn];
int a, b, n, m, s, t, cnt -1;
queue int q;void addedge( int u, int v, int flow, int cost ) {E[ cnt] { v, head[u], flow, cost }; head[u] cnt;E[ cnt] { u, head[v], 0, -cost }; head[v] cnt;
}bool SPFA() {memset( lst, -1, sizeof( lst ) );memset( dis, 0x3f, sizeof( dis ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}int MCMF() {int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i ^ 1].flow flow;E[i].flow - flow;ans E[i].cost;}}return ans;
}int id( int x, int y ) { return ( x - 1 ) * m y; }signed main() {memset( head, -1, sizeof( head ) );scanf( %lld %lld %lld %lld, a, b, n, m );n , m ;s 0, t n * m 1;int num t;for( int i 1;i n;i )for( int j 1, x;j m;j ) {scanf( %lld, x );addedge( id( i, j ), id( i, j 1 ), 1, -x );addedge( id( i, j ), num, inf, 0 );addedge( num, id( i, j 1 ), inf, 0 );}for( int j 1;j m;j )for( int i 1, x;i n;i ) {scanf( %lld, x );addedge( id( i, j ), id( i 1, j ), 1, -x );addedge( id( i, j ), num, inf, 0 );addedge( num, id( i 1, j ), inf, 0 );}for( int i 1, k, x, y;i a;i ) {scanf( %lld %lld %lld, k, x, y );x , y ;addedge( s, id( x, y ), k, 0 );}for( int i 1, k, x, y;i b;i ) {scanf( %lld %lld %lld, k, x, y );x , y ;addedge( id( x, y ), t, k, 0 );}printf( %lld\n, -MCMF() );return 0;
}航空路线问题
luogu-P2770
显然不可能让网络流跑一个环流会死循环。
所以把这个回来也变成过去限制每个点只能经过一次起点和终点可以经过两次。
限制的是点不是关系拆点跑最大流输出方案。
#include bits/stdc.h
using namespace std;
#define maxn 205
#define maxm 100000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow, cost; }E[maxm];
int dis[maxn], lst[maxn], head[maxn];
bool vis[maxn];
queue int q;
map string, int id;
map int, string ch;
int n, m, cnt -1, s, t;void addedge( int u, int v, int flow, int cost ) {E[ cnt] { v, head[u], flow, cost }; head[u] cnt;E[ cnt] { u, head[v], 0, -cost }; head[v] cnt;
}bool SPFA() {memset( dis, 0x3f, sizeof( dis ) );memset( lst, -1, sizeof( lst ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}int MCMF() {int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] )E[i].flow - flow, E[i ^ 1].flow flow;ans flow;}return ans;
}vector int ret[2];
bool flag;
void dfs( int u, int w ) {for( int i head[u];~ i and ! flag;i E[i].nxt ) {if( E[i ^ 1].flow ) {E[i ^ 1].flow --;if( E[i].to u n ) ret[w].push_back( u ), dfs( E[i].to, w ), flag 1;else if( u n and E[i].to ^ u - n and E[i].to ^ s ) dfs( E[i].to, w ), flag 1;}}
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d, n, m );string name1, name2; s n 1 | 1, t s 1;for( int i 1;i n;i ) {cin name1;ch[id[name1] i] name1;if( i ^ 1 and i ^ n ) addedge( i, i n, 1, -1 );else addedge( i, i n, 2, -1 );}for( int i 1;i m;i ) {cin name1 name2;int x id[name1], y id[name2];if( x y ) swap( x, y );if( x 1 and y n ) addedge( x n, y, 2, 0 );else addedge( x n, y, 1, 0 );}addedge( s, 1, 2, 0 );addedge( n 1, t, 2, 0 );if( MCMF() ^ 2 ) return ! printf( No Solution!\n );flag 0;dfs( s, 0 );flag 0;dfs( s, 1 );printf( %d\n, ret[0].size() ret[1].size() - 2 );for( int i 0;i ret[0].size();i ) cout ch[ret[0][i]] endl;for( int i ret[1].size() - 2;~ i;i -- ) cout ch[ret[1][i]] endl;return 0;
}火星探险问题
luogu-P3356
这道题和《深海机器人》是一样的只不过这道题的权值是点权而非边权且不是每个点都有。
所以需要拆点。[1,P∗Q][1,P*Q][1,P∗Q] 是普通点[P∗Q1,P∗Q∗2][P*Q1,P*Q*2][P∗Q1,P∗Q∗2] 是有石块点。这里同样的石块点只能贡献一次连接石块点的边流量限制为 111。
这里输出方案因为车数量少图小直接最后 dfs\text{dfs}dfs 走被流量流过的边用 setsetset 记录每个位置到达的车编号。
#include bits/stdc.h
using namespace std;
#define maxn 5000
#define maxm 1000000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow, cost, dir; }E[maxm];
int ch[maxn][maxn];
int lst[maxn], dis[maxn], head[maxn];
bool vis[maxn];
int n, P, Q, S, T, cnt -1;
queue int q;void addedge( int u, int v, int flow, int cost ) {E[ cnt] { v, head[u], flow, cost, 1 }; head[u] cnt;E[ cnt] { u, head[v], 0, -cost, 0 }; head[v] cnt;
}bool SPFA() {memset( dis, 0x3f, sizeof( dis ) );memset( lst, -1, sizeof( lst ) );dis[S] 0; q.push( S );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[T];
}void MCMF() {while( SPFA() ) {int flow inf;for( int i lst[T];~ i;i lst[E[i ^ 1].to] ) flow min( flow, E[i].flow );for( int i lst[T];~ i;i lst[E[i ^ 1].to] )E[i].flow - flow, E[i ^ 1].flow flow;}
}int id( int x, int y ) { return ( x - 1 ) * Q y; }bool print( int x, int y, int i ) {if( x 1 or x P * Q or y 1 or y P * Q ) return 0;if( y x 1 ) printf( %d 1\n, i );else printf( %d 0\n, i );return 1;
}set int s[maxn];void dfs( int x, int lst ) {for( int i head[x];~ i;i E[i].nxt )if( E[i ^ 1].flow and E[i].dir ) {bool flag 1;while( E[i ^ 1].flow and s[x].size() ) {E[i ^ 1].flow --;flag print( ( 1 x and x P * Q ) ? x : lst, E[i].to, *s[x].begin() );s[E[i].to].insert( *s[x].begin() );s[x].erase( s[x].begin() );}dfs( E[i].to, flag ? lst : x );}
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d %d, n, Q, P );for( int i 1;i P;i )for( int j 1;j Q;j )scanf( %d, ch[i][j] );addedge( S, 1, n, 0 );#define ID id( i, j )for( int i 1;i P;i )for( int j 1;j Q;j ) {if( j ^ Q and ch[i][j 1] ^ 1 )addedge( ID, id( i, j 1 ), inf, 0 );if( i ^ P and ch[i 1][j] ^ 1 )addedge( ID, id( i 1, j ), inf, 0 );}for( int i 1;i P;i )for( int j 1;j Q;j ) {if( j ^ Q and ch[i][j 1] 2 )addedge( ID, id( i, j 1 ) P * Q, inf, 0 );if( i ^ P and ch[i 1][j] 2 )addedge( ID, id( i 1, j ) P * Q, inf, 0 );}for( int i 1;i P;i )for( int j 1;j Q;j )if( ch[i][j] 2 ) addedge( id( i, j ) P * Q, id( i, j ), 1, -1 );T P * Q 1 | 1;addedge( P * Q, T, inf, 0 );MCMF();for( int i 1;i n;i ) s[1].insert( i );dfs( 1, 0 );return 0;
}小结Ⅱ。
太空飞行计划问题
luogu-P2762
这里的限制不能用小结Ⅰ的方法理解了。
因为这里的限制是一堆绑定少了其中一个都不行。
我们就用最小割的角度来看。
还是实验左部点元件右部点与源点汇点的连边上带花费。
如果一条边被流看作是断掉了这条边。
最后跑最大流割裂源点和汇点不再在同一个连通块。
这其实是最大权闭合子图我以前写过详细的内容。
这里主要是有新的方案输出方法。
我们考虑怎么判断的流不动了——bfs\text{bfs}bfs 无法走到汇点。
这其实是通过网络流 bfs\text{bfs}bfs 的分层图来判断的。
在最后我们只需要看这些元件是否在分层图中被标号了就知道其是否与源点连通。
#include bits/stdc.h
using namespace std;
#define maxn 105
#define maxm 30000
#define int long long
#define inf 0x3f3f3f3f
int n, m, cnt -1, s, t;
struct node { int to, nxt, flow; }E[maxm];
int head[maxn], dep[maxn], cur[maxn];
bool vis[maxn];
queue int q;
vector int G[maxn];void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w }; head[u] cnt;E[ cnt] { u, head[v], 0 }; head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {int v E[i].to; cur[u] i;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}signed main() {memset( head, -1, sizeof( head ) );scanf( %lld %lld, m, n );s 0, t n m 1; int ans 0;for( int i 1, x;i m;i ) {scanf( %lld, x );addedge( s, i, x );ans x;char tools[10000];memset( tools, 0, sizeof( tools ) );cin.getline( tools, 10000 );int ulen 0, tool;while( sscanf( tools ulen, %lld , tool ) 1 ) {G[i].push_back( tool );addedge( i, tool m, inf );if( tool 0 ) ulen ;else while( tool ) tool / 10, ulen ;ulen ;}}for( int i 1, x;i n;i ) {scanf( %lld, x );addedge( i m, t, x );}while( bfs() ) ans - dfs( s, inf );for( int i 1;i m;i )if( dep[i] ) printf( %lld , i );puts();for( int i 1;i n;i ) if( dep[i m] ) printf( %lld , i );puts();printf( %lld\n, ans );return 0;
}方格取数问题
luogu-P2774
将每个格子拆成选 iii 和不选 ininin 两个点。
u,vu,vu,v 两点代表的格子有共同边连边无穷 (u,vn),(v,un)(u,vn),(v,un)(u,vn),(v,un)选点和源点连边不选点和汇点连边。
从最小割角度理解跑费用流。
最后看和 SSS 在同一个集合的点的值。
#include bits/stdc.h
using namespace std;
#define maxn 20005
#define maxm 50000
#define int long long
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow; }E[maxm];
int dep[maxn], cur[maxn], a[maxn], head[maxn];
bool vis[maxn];
queue int q;
int n, m, s, t, cnt -1;void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w }; head[u] cnt;E[ cnt] { u, head[v], 0 }; head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( ! cap or u t ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {int v E[i].to; cur[u] i;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int id( int x, int y ) { return ( x - 1 ) * n y; }signed main() {memset( head, -1, sizeof( head ) );scanf( %lld %lld, m, n );s 0, t n * m 1 | 1;for( int i 1;i m;i )for( int j 1;j n;j )scanf( %lld, a[id( i, j )] );for( int i 1;i m;i )for( int j 1;j n;j ) {addedge( s, id( i, j ), a[id( i, j )] );addedge( id( i, j ) n * m, t, a[id( i, j )] );}for( int i 1;i m;i )for( int j 1;j n;j ) {if( i ^ 1 ) addedge( id( i, j ), id( i - 1, j ) n * m, inf );if( j ^ 1 ) addedge( id( i, j ), id( i, j - 1 ) n * m, inf );if( i ^ m ) addedge( id( i, j ), id( i 1, j ) n * m, inf );if( j ^ n ) addedge( id( i, j ), id( i, j 1 ) n * m, inf );}while( bfs() ) dfs( s, inf );int ans 0;for( int i 1;i m;i )for( int j 1;j n;j )if( dep[id( i, j )] ) ans a[id( i, j )];printf( %lld\n, ans );return 0;
}骑士共存问题
选了一个点意味着一些点的不选择。
在《太空飞行计划问题》中选了一个点就要选择一些点与这道题恰恰相反当时我们是最小割入手。
在《方格取数问题》中与本题是同类题我们是从拆点最小割入手。
这道题我们当然可以同上一题的做法但这道题的特殊性质提供了一种新方法。
一个点横纵坐标和和其攻击点的横纵坐标和奇偶性一定不同。
将这个棋盘变成二分图按 xyxyxy 奇偶分类。
选了一个点意味着不选一些点我反而将这种关系体现成边。
这些边一定是连接左右部点的边。
假设奇为左部点偶为右部点在新图上跑最大匹配。
先假设所有点都选择此时一个匹配意味着什么意味着有一对关系冲突。
那么我只需要删掉其中一个点即可。
所以总点数减去最大匹配恰恰就是可选的最大点数
#include bits/stdc.h
using namespace std;
#define maxn 40005
#define maxm 500000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow; }E[maxm];
int n, m, s, t, cnt -1;
int dep[maxn], cur[maxn], head[maxn];
bool vis[maxn];
queue int q;bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( ! cap or u t ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {int v E[i].to; cur[u] i;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}void addedge( int u, int v, int w ) {if( vis[u] or vis[v] ) return;E[ cnt] { v, head[u], w }, head[u] cnt;E[ cnt] { u, head[v], 0 }, head[v] cnt;
}int id( int x, int y ) { return ( x - 1 ) * n y; }int main() {memset( head, -1, sizeof( head ) );scanf( %d %d, n, m );for( int i 1, x, y;i m;i ) {scanf( %d %d, x, y );vis[id( x, y )] 1;}s 0, t n * n 1;for( int i 1;i n;i )for( int j 1;j n;j )if( ( i j ) 1 ) {addedge( s, id( i, j ), 1 );if( i 2 and j 1 ) addedge( id( i, j ), id( i - 2, j - 1 ), inf );if( i 2 and j n ) addedge( id( i, j ), id( i - 2, j 1 ), inf );if( i 1 and j 2 ) addedge( id( i, j ), id( i - 1, j - 2 ), inf );if( i 1 and j n - 1 ) addedge( id( i, j ), id( i - 1, j 2 ), inf );if( i n and j 2 ) addedge( id( i, j ), id( i 1, j - 2 ), inf );if( i n and j n - 1 ) addedge( id( i, j ), id( i 1, j 2 ), inf );if( i n - 1 and j 1 ) addedge( id( i, j ), id( i 2, j - 1 ), inf );if( i n - 1 and j n ) addedge( id( i, j ), id( i 2, j 1 ), inf );}else addedge( id( i, j ), t, 1 );int ans n * n - m;while( bfs() ) ans - dfs( s, inf );printf( %d\n, ans );return 0;
}小结ⅠⅡ补充。
最长不下降子序列问题
luogu-P2766
先 dpdpdp 求出最长不下降子序列长度。
每个点只能用一次的情况下有多少个最长不下降子序列。
限制点拆点加边。而且求的是最长。
我们考虑 dpdpdp 转移式子只有 dpj1dpijidp_{j}1dp_i\quad jidpj1dpiji 才意味着 jjj 可能和 iii 在同一个最长不下降子序列内。
按照这种条件进行连边。
这有点“分层”的意味了
dpidp_idpi 相同的为一层每条边都是相邻两层间的边且是上一层指向下一层。
符合要求的答案一定在最后一层开头从第一层开始。
我们在第一层上方单建一层只放源点最后一层下方单建一层只放汇点。
这只是脑子里形成的分层哦~代码里还是感觉是一坨
分层图就是本层内是不存在边的边都不是一层中的某点连向另一层的某点。
由《魔术球问题》知学得了在残余网络上加边继续判解存在性问题。
这里不用向《数字梯形问题》每次都重建那只是刚开始为了方便理解
我们直接在第二个子问题跑完后另给 1,n1,n1,n 号点加入无限制的边继续跑。
#include bits/stdc.h
using namespace std;
#define maxn 1005
#define maxm 300000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow; }E[maxm];
int head[maxn], cur[maxn], dep[maxn];
bool vis[maxn];
queue int q;
int n, s, t, cnt, S, T;
int x[maxn], dp[maxn];void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w }, head[u] cnt;E[ cnt] { u, head[v], 0 }, head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( E[i].flow, cap ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, inf );return ans;
}int main() {scanf( %d, n );for( int i 1;i n;i ) scanf( %d, x[i] );if( n 1 ) return ! printf( 1\n1\n1\n );int ans 0;for( int i 1;i n;i ) {dp[i] 1;for( int j 1;j i;j )if( x[j] x[i] ) dp[i] max( dp[i], dp[j] 1 );ans max( ans, dp[i] );}printf( %d\n, ans );s 0, t n 1 | 1, cnt -1;memset( head, -1, sizeof( head ) );for( int i 1;i n;i ) {addedge( i, i n, 1 );if( dp[i] 1 ) addedge( s, i, 1 );if( dp[i] ans ) addedge( i n, t, 1 );for( int j i 1;j n;j )if( dp[i] 1 dp[j] and x[i] x[j] ) addedge( i n, j, 1 );}int ret dinic();printf( %d\n, ret );addedge( s, 1, inf ), addedge( 1, n 1, inf );if( dp[n] ans ) addedge( n, n 1, inf ), addedge( n 1, t, inf );printf( %d\n, ret dinic() );return 0;
}孤岛营救问题
luogu-P4011
分层。设计 2p2^p2p 层每层表示身上所有钥匙的状态第 iii 层二进制 jjj 为 111 表示当前状态有 jjj 类钥匙。
每层根据钥匙的拥有不同能到达的状态层这个层可就不一定是相邻了也不同能到达的状态层中的位置也不同。
#include bits/stdc.h
using namespace std;
#define maxn 200000
#define maxm 2000000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow, cost; }E[maxm];
int head[maxn], lst[maxn], dis[maxn];
bool vis[maxn];
queue int q;
int N, M, K, P, S, s, t, cnt -1;void addedge( int u, int v, int w, int c ) {E[ cnt] { v, head[u], w, c }, head[u] cnt;E[ cnt] { u, head[v], 0,-c }, head[v] cnt;
}bool SPFA() {memset( dis, 0x3f, sizeof( dis ) );memset( lst, -1, sizeof( lst ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}void MCMF( int maxflow, int mincost ) {maxflow mincost 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i].flow - flow;E[i ^ 1].flow flow;mincost flow * E[i].cost;}maxflow flow;}
}pair int, int key[150][150];
int id( int x, int y ) { return ( x - 1 ) * M y; }
bool flag[150];
int tot[150];
int g[150][150];void build() {s 0, t (1 P) * N * M 1; flag[0] 1;for( int sta 0;sta (1 P);sta ) {for( int i 1;i P;i )if( (1 i - 1) sta ) flag[i] 1;else flag[i] 0;for( int i 1;i N;i )for( int j 1;j M;j ) {if( j M and ~ g[id(i, j)][id(i, j 1)] and flag[g[id(i, j)][id(i, j 1)]] ) {addedge( sta * N * M id(i, j), N * M * sta id(i, j 1), inf, 1 );addedge( sta * N * M id(i, j 1), N * M * sta id(i, j), inf, 1 );}if( i N and ~ g[id(i, j)][id(i 1, j)] and flag[g[id(i 1, j)][id(i, j)]] ) {addedge( sta * N * M id(i, j), N * M * sta id(i 1, j), inf, 1 );addedge( sta * N * M id(i 1, j), N * M * sta id(i, j), inf, 1 );}if( i N and j M ) addedge( sta * N * M id(i, j), t, inf, 0 );}for( int i 1;i P;i )if( ! flag[i] ) {int nxt sta (1 i - 1);for( int j 1;j tot[i];j ) {int x id(key[i][j].first, key[i][j].second);addedge( N * M * sta x, N * M * nxt x, inf, 0 );}}}addedge( s, 1, 1, 0 );
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d %d %d, N, M, P, K );for( int i 1, x, y, id1, id2;i K;i ) {scanf( %d %d, x, y );id1 id( x, y );scanf( %d %d, x, y );id2 id( x, y );scanf( %d, x );if( ! x ) x -1;g[id1][id2] g[id2][id1] x;}scanf( %d, S );for( int i 1, x, y, p;i S;i ) {scanf( %d %d %d, x, y, p );key[p][ tot[p]] make_pair( x, y );}build();int flow, cost;MCMF( flow, cost );if( flow ^ 1 ) puts(-1);else printf( %d\n, cost );return 0;
}汽车加油行驶问题
luogu-P4009
按油量分层第 iii 层表示油量剩余 iii。翻译题目中的边即可。
000 层一定要加油回到油满层。
#include bits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define int long long
#define maxn 300000
#define maxm 4000000
struct node { int to, nxt, flow, cost; }E[maxm];
int dis[maxn], lst[maxn], head[maxn];
bool vis[maxn];
int s, t, cnt -1;
queue int q;void addedge( int u, int v, int w, int c ) {E[ cnt] { v, head[u], w, c }, head[u] cnt;E[ cnt] { u, head[v], 0,-c }, head[v] cnt;
}bool SPFA() { memset( lst, -1, sizeof( lst ) );memset( dis, 0x3f, sizeof( dis ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~lst[t];
}int MCMF() {int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i].flow - flow;E[i ^ 1].flow flow;ans E[i].cost * flow;}}return ans;
}int fuel[105][105];
int N, K, A, B, C;int id( int x, int y, int k ) { return k * N * N ( x - 1 ) * N y; }void build() {memset( head, -1, sizeof( head ) );s 0, t id(N, N, K) 1;addedge(s, id(1, 1, K), 1, 0 );for( int k 0;k K;k ) {//第k层表示剩余油量为kfor( int i 1;i N;i ) {for( int j 1;j N;j ) {if( i N and j N ) addedge( id(i, j, k), t, inf, 0 );if( fuel[i][j] and k ^ K ) {addedge( id(i, j, k), id(i, j, K), inf, A );continue;}if( k ) {if( i ^ 1 ) addedge( id(i, j, k), id(i - 1, j, k - 1), inf, B );if( j ^ 1 ) addedge( id(i, j, k), id(i, j - 1, k - 1), inf, B );if( i ^ N ) addedge( id(i, j, k), id(i 1, j, k - 1), inf, 0 );if( j ^ N ) addedge( id(i, j, k), id(i, j 1, k - 1), inf, 0 );}else addedge( id(i, j, k), id(i, j, K), inf, A C );}}}
}signed main() {scanf( %lld %lld %lld %lld %lld, N, K, A, B, C );for( int i 1;i N;i )for( int j 1;j N;j )scanf( %lld, fuel[i][j] );build();printf( %lld\n, MCMF() );return 0;
}[CTSC1999]家园 / 星际转移问题
luogu-P2754
先用并查集判断地球源点和月球汇点是否联通。
按时间分层枚举答案同时建层不再是一开始就建完了船的停留站点是个循环。
每一次都跑网络流统计流到汇点的流量当达到总人数时证明全部运送完了。
#include bits/stdc.h
using namespace std;
#define maxn 1000000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow; }E[maxn];
int dep[maxn], cur[maxn], head[maxn];
int h[200], r[200], g[200][200];
int cnt -1, s, t, n, m, k;
queue int q;void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w }, head[u] cnt;E[ cnt] { u, head[v], 0 }, head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1, q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( ! cap or u t ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {int v E[i].to; cur[u] i;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, inf );return ans;
}namespace DSU {int f[maxn];void init() { for( int i 1;i n 2;i ) f[i] i; }int find( int x ) { return f[x] x ? x : f[x] find( f[x] ); }void merge( int x, int y ) { x find( x ), y find( y ); if( x ^ y ) f[y] x; }
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d %d, n, m, k );DSU :: init();for( int i 1;i m;i ) {scanf( %d %d, h[i], r[i] );for( int j 0;j r[i];j ) {scanf( %d, g[i][j] );if( g[i][j] 0 ) g[i][j] n 1;if( g[i][j] -1 ) g[i][j] n 2;if( j ) DSU :: merge( g[i][j - 1], g[i][j] );}}if( DSU :: find( n 1 ) ^ DSU :: find( n 2 ) ) return ! printf( 0\n );s 0, t maxn - 1; int flow 0;for( int ans 1;;ans ) {addedge( s, (ans - 1) * (n 1) n 1, inf ); //第ans秒的地球编号for( int i 1;i m;i ) { //往下一层建边int x (ans - 1) % r[i], y ans % r[i];if( g[i][x] n 2 ) x t;else x (ans - 1) * (n 1) g[i][x];if( g[i][y] n 2 ) y t;else y ans * (n 1) g[i][y];addedge( x, y, h[i] );}flow dinic();if( flow k ) return ! printf( %d\n, ans );for( int i 1;i n 1;i )addedge( (ans - 1) * (n 1) i, ans * (n 1) i, inf );}return 0;
}小结Ⅲ。
餐巾计划问题
luogu-P1251
按天分层建图。
将每天拆成起始点和结束点。
送到快洗部属于结束点操作连向 imimim 天后的起始点带费用。送到慢洗部属于结束点操作连向 ininin 天后的起始点带费用。延期送洗属于结束点操作连向 i1i1i1 天的结束点不带费用。购买新的餐巾的操作也应是连向每天起始点的边目前没有确定从哪连但带费用。
网络流的建图一定有顺序的建的边一定是沿源点流向汇点方向才能流通且不环流。
发现上面的建边都是从一天的结束点到后面天的起始点/结束点且每天起始点没有往后面的天连点。
所以应当是源点向结束点连边起始点向汇点连边。新毛巾就是源点向起始点连边。
#include bits/stdc.h
using namespace std;
#define inf 0x7f7f7f7f
#define int long long
#define maxn 600000
struct node { int to, nxt, flow, cost; }E[maxn];
int head[maxn], dis[maxn], lst[maxn];
bool vis[maxn];
queue int q;
int cnt -1, s, t;void addedge( int u, int v, int flow, int cost ) {E[ cnt] { v, head[u], flow, cost }, head[u] cnt;E[ cnt] { u, head[v], 0, -cost }, head[v] cnt;
}bool SPFA() {memset( dis, 0x7f, sizeof( dis ) );memset( lst, -1, sizeof( lst ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}int MCMF() {int cost 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i ^ 1].flow flow;E[i].flow - flow;cost flow * E[i].cost;}}return cost;
}signed main() {memset( head, -1, sizeof( head ) );int n; scanf( %lld, n );s 0, t n 1 | 1;//[1,n]表示晚上 [n1,2n]表示白天for( int i 1, x;i n;i ) {scanf( %lld, x );addedge( s, i, x, 0 ); //第i天晚上得到x张脏餐巾addedge( i n, t, x, 0 ); //第i天早上有x张干净餐巾可用}int P, M, F, N, S;scanf( %lld %lld %lld %lld %lld, P, M, F, N, S );for( int i 1;i n;i ) {if( i 1 n ) addedge( i, i 1, inf, 0 ); //第i天晚上的脏餐巾可以留到i1天晚上if( i M n ) addedge( i, i M n, inf, F ); //送去快洗部 在第iM天早上得到干净餐巾if( i N n ) addedge( i, i N n, inf, S ); //送去慢洗部 在第iN天早上得到干净餐巾addedge( s, i n, inf, P ); //直接在第i天早上购买新餐巾}printf( %lld\n, MCMF() );return 0;
}小结Ⅲ。
最长k可重区间集问题
luogu-P3358
每个点被覆盖当且仅当线段的起点或者终点被覆盖那么可以离散成点因为一条线段的中间的点是不必要的。
对于每个点其最多被覆盖 kkk 次也就是说一条线段能覆盖好多点但是一个点最多被覆盖 kkk 次。
如果我们将每条线段连向源点表示使用当前这条线段而这条线段需要连向自己覆盖的那些点这些点连向汇点容量为 kkk 表示自己最多被覆盖 kkk 次。
我们让最终被覆盖的点通过汇点的流量限制保证这个条件但是这并不正确。
因为这是费用流这条线段的花费肯定是其长度而流量为 111如果流量 111 的话费用将会被统计的不正确但是为 111 的话一条线段的流必然流向某个点但是我们想让这一条流流过所有的点怎么办
可以发现这变成了一个一流对多流的问题问题自然也被转换成了如何使用一条流流过若干个点发现想要这么做必然这些点得横着连到一块然后使用一条流流过他们所以就有本题的基本模型了把点串联起来。
我们从源点放出 kkk 流所以每个相邻两点之间连上容量为 kkk 费用为 000 的边 然后线段连接 lll 和 rrr离散化费用为其长度跑费用流即可。
#include bits/stdc.h
using namespace std;
#define maxn 1005
#define maxm 20000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow, cost; }E[maxm];
int dis[maxn], lst[maxn], head[maxn], l[maxn], r[maxn], len[maxn], x[maxn];
bool vis[maxn];
queue int q;
int n, k, s, t, cnt -1;void addedge( int u, int v, int w, int c ) {E[ cnt] { v, head[u], w, c }; head[u] cnt;E[ cnt] { u, head[v], 0, -c }; head[v] cnt;
}bool SPFA() {memset( lst, -1, sizeof( lst ) );memset( dis, 0x3f, sizeof( dis ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}int MCMF() {int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] )E[i ^ 1].flow flow, E[i].flow - flow, ans flow * E[i].cost;}return ans;
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d, n, k );for( int i 1;i n;i ) {scanf( %d %d, l[i], r[i] );x[i] l[i], x[i n] r[i];len[i] r[i] - l[i];}sort( x 1, x ( n 1 | 1 ) );int m unique( x 1, x ( n 1 | 1 ) ) - x - 1;for( int i 1;i n;i ) {l[i] lower_bound( x 1, x m 1, l[i] ) - x;r[i] lower_bound( x 1, x m 1, r[i] ) - x;}s 0, t m 1;for( int i 1;i m;i ) {if( i 1 ) addedge( s, i, k, 0 );else if( i m ) addedge( i, t, k, 0 ), addedge( i - 1, i, k, 0 );else addedge( i - 1, i, k, 0 );}for( int i 1;i n;i ) addedge( l[i], r[i], 1, -len[i] );printf( %d\n, -MCMF() );return 0;
}最长k可重线段集问题
如果 yyy 各不相同完全可以拍成 xxx 轴上的问题就转化到上一题了。
那我们直接换种表示方法在 xxx 轴上表示一个线段
在数轴上比较简单的方式就是扩域。
每个线段 iii 的左右端点 (li,ri)(l_i,r_i)(li,ri) 变换成 (2×li,2×ri)(2\times l_i,2\times r_i)(2×li,2×ri)这样的话就相当于每个下标多了一个空间。
那么对于一个左右端点相同的区间 (x,x)(x,x)(x,x)就可以连边成 (2x,2x1)(2x,2x 1)(2x,2x1)。
但这样的话原本左右端点不用的区间也要改。
由于那些相同的区间右端点加了 111所以如果存在这样两个线段 (p,p),(p,q)(p,p),(p,q)(p,p),(p,q)那么原本不交的两个区间在扩域之后变成了相交的 (2p,2p1),(2p,2q)(2p,2p1),(2p,2q)(2p,2p1),(2p,2q) 。
处理方式很简单对于一个 p̸qp\notqpq 的区间 (p,q)(p,q)(p,q)连边 (2p1,2q)(2p1,2q)(2p1,2q) 即可。
对于原本存在的两个均不垂直 xxx 轴的线段他们如果相交那么交的那一端r1−l2≥1r_1-l_2\ge 1r1−l2≥1如果不交那么有 l2−r1≥1l_2-r_1\ge 1l2−r1≥1。
扩域之后就变成了 ≥2\ge 2≥2 。
所以如果只是左端点增加 111 根本不影响判定。
#include bits/stdc.h
using namespace std;
#define maxn 1005
#define maxm 20000
#define inf 0x3f3f3f3f
struct node { int to, nxt, flow, cost; }E[maxm];
int dis[maxn], lst[maxn], head[maxn], l[maxn], r[maxn], len[maxn], x[maxn];
bool vis[maxn];
queue int q;
int n, k, s, t, cnt -1;void addedge( int u, int v, int w, int c ) {E[ cnt] { v, head[u], w, c }; head[u] cnt;E[ cnt] { u, head[v], 0, -c }; head[v] cnt;
}bool SPFA() {memset( lst, -1, sizeof( lst ) );memset( dis, 0x3f, sizeof( dis ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}int MCMF() {int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] )E[i ^ 1].flow flow, E[i].flow - flow, ans flow * E[i].cost;}return ans;
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d, n, k );for( int i 1;i n;i ) {scanf( %d %d, l[i], r[i] );x[i] l[i], x[i n] r[i];len[i] r[i] - l[i];}sort( x 1, x ( n 1 | 1 ) );int m unique( x 1, x ( n 1 | 1 ) ) - x - 1;for( int i 1;i n;i ) {l[i] lower_bound( x 1, x m 1, l[i] ) - x;r[i] lower_bound( x 1, x m 1, r[i] ) - x;}s 0, t m 1;for( int i 1;i m;i ) {if( i 1 ) addedge( s, i, k, 0 );else if( i m ) addedge( i, t, k, 0 ), addedge( i - 1, i, k, 0 );else addedge( i - 1, i, k, 0 );}for( int i 1;i n;i ) addedge( l[i], r[i], 1, -len[i] );printf( %d\n, -MCMF() );return 0;
}负载平衡问题
luogu-P4016
就是个结论题非要包装成网络流那我们就已知答案反推网络流写法
将 ai−avea_i-aveai−ave 分成正负两部分源点流给负的表示“需要”正的流给汇点表示“传递”。
编号相邻点之间连边即可。
结论为什么正确不是本篇博客讨论重点略过。
#include bits/stdc.h
using namespace std;
#define maxn 105
#define maxm 5005
#define inf 0x3f3f3f3f
int n, s, t, cnt -1;
int a[maxn], dis[maxn], lst[maxn], head[maxn];
bool vis[maxn];
struct node { int to, nxt, flow, cost; }E[maxm];
queue int q;void addedge( int u, int v, int w, int c ) {E[ cnt] { v, head[u], w, c }, head[u] cnt;E[ cnt] { u, head[v], 0, -c }, head[v] cnt;
}bool SPFA() {memset( dis, 0x3f, sizeof( dis ) );memset( lst, -1, sizeof( lst ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}void MCMF() {int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i ^ 1].flow flow;E[i].flow - flow;ans flow * E[i].cost;}}printf( %d\n, ans );
}int main() {memset( head, -1, sizeof( head ) );scanf( %d, n );int ave 0;for( int i 1;i n;i )scanf( %d, a[i] ), ave a[i];ave / n;s 0, t n 1;for( int i 1;i n;i ) {if( a[i] ave ) addedge( i, t, a[i] - ave, 0 );if( a[i] ave ) addedge( s, i, ave - a[i], 0 );addedge( i, i n ? 1 : i 1, inf, 1 );addedge( i, i 1 ? n : i - 1, inf, 1 );}MCMF();return 0;
}软件补丁问题
luogu-P2761
就是个最短路问题不懂为啥是在二十四题内也许是因为可以硬套成一个流量为 111 的最小费用流。
#include bits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
int dis[4000000], vis[4000000];
int b1[1000], b2[1000], f1[1000], f2[1000], w[1000];
char a[1000], b[1000];
int n, m;
queue int q;void SPFA() {int s (1 n) - 1, t 0;memset( dis, 0x3f, sizeof( dis ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i 1;i m;i )if( (b1[i] u) b1[i] and !(b2[i] u) ) {int v ((u | f1[i]) ^ f1[i]) | f2[i];if( dis[v] dis[u] w[i] ) {dis[v] dis[u] w[i];if( ! vis[v] ) vis[v] 1, q.push( v );}}}if( dis[t] inf ) printf( 0\n );else printf( %d\n, dis[t] );
}int main() {scanf( %d %d, n, m );for( int i 1;i m;i ) {scanf( %d %s %s, w[i], a, b );for( int j 0;j n;j ) {switch( a[j] ) {case : b1[i] | (1 j); break;case - : b2[i] | (1 j); break;case 0 : break;}switch( b[j] ) {case - : f1[i] | (1 j); break;case : f2[i] | (1 j); break;case 0 : break;}}}SPFA();return 0;
}总结 网络流是“单向”的类比水流一旦建图形成环就会无限流下去。 所以有些题目的路程看似是一条回路也得拆成两条单向路。 网络流是“定向”的从源点流向汇点方向。 对于边无穷流量设计的理解 如果是从最大流角度那么意味着这条边是可以随便走的不被限制也不限制其余边。这条边对应的信息可以无限次数地使用。如果是从最小割角度那么意味着这条边连接的两个点的信息是被绑定在一起的无法分开。一般在”这个东西选/不选“问题中出现。 碰到不是“一个单位时间”的问题例如多天多个小时往往考察分层图。 如果一个“点”带了两个独立的属性限制与花费往往是考察费用流。一个成为边流量一个成为边花费。 如果一个点只有花费属性就变成流量还是跑最大流。 点权题往往意味着拆点变边权。网络流是没有“点权”这一概念的。
小结Ⅰ
最大流角度 每个点都有限制限制将变成网络流上的“流量”。 这个限制是只针对自己的那么就会将且是与源/汇点的边上的。这个限制是针对“关系”的就是两个点的连边上。其余为 infinfinf。 所求的花费和价值都变成网络流上的“花费”。 “花费”针对“关系”时就在两个点的连边上。针对是否选择该点时就在与源/汇点的边上。其余为 000。 当全体都无限制的时候肯定会有大背景下的限制比如求 mmm 种只有 mmm 个人什么的。 这个时候就是源点向唯一起点的边流量限制成 mmm。 如果起点不唯一那么还得新建一个超级起点源点向超级起点限制超级起点向所有起点建边无穷。 这是为了统一起点至于为什么解释与《飞行员配对方案问题》中所述问题同理。
小结Ⅱ
网络流很常见的技巧——拆点。拆点往往有着一定的暗示 同一种“选择”不同时刻经过同一个点同一条边但其中有一些会自带独立属性前几次会有贡献之类的 这个时候往往将选择拆成有贡献的选择和无贡献的选择。 通过流量限制“选择”的次数。 一般这种边都可以形象的表示∘→∘\circ\rightarrow\circ∘→∘ 变成了 ∘↗∘↘∘_\circ\nearrow^\circ\searrow_\circ∘↗∘↘∘ 一定要记得连回来 状态不同到达同一个位置自身属性不同钥匙油量等 会将一个点的每一个不同状态都拆成一个点。
网络流的方案输出问题。 根据反向边流量来看。流的角度 这条边流了那么反向边一定有流量增加。 根据 S,TS,TS,T 集合划分来看割的角度 判断是否 bfs\text{bfs}bfs 有层编号便可知道能否从 SSS 走到这个点。 但有的时候根据反向边流量来看可能会出错。一般是把花费当成流量的题上。
小结Ⅰ、Ⅱ 补充
最小割角度
往往是出现价值花费的时候建图的边是从最小割方面理解。
通常对于一条流过的边在最大流角度意味着“选择”在最小割角度意味着“放弃”。
不管是流角度还是割角度一条流通路上的流量一定是由路上边的最小流量决定的。
会发现输出方案有的题是选择割的角度有的是流的角度真的每道题两种角度都适用吗
对于绑定选择拆点的问题
如果把点拆成选和不选分成二分图选与 SSS 联通不选与 TTT 联通。
最小割来理解你会发现如果绑定是单向的跑出来就打错特错了。
单向即选 a 必不选 b但是选 b 没要求不能选 a。
双向即选a不能选 b选 b也不能选 a。
觉得有点怪是吧其实是因为不能绑定互斥关系导致的。
你想一个点拆成选和不选那么势必这两个拆点之间不会连边对于一个限制关系将 uuu 选点和 vvv 不选点绑定在一起而不绑定 vvv 选点和 uuu 不选点。那跑二分图最大完备匹配后就无法得知最大价值了。
如果我们从流的角度算所有的流通路上的值和很有可能某个点选和不选在不同的流通路上这就废了。
如果我们从割的角度看所有与源点联通的值和那也完了可能割掉的是某个点不选到汇点边这条流量最小本身这个点选和不选也不连通代表选意义的点可能也在源点集合那不还是将冲突的两个点都选了。
而如果这个绑定是双向的那么对于对于一对关系 x,yx,yx,y 以 xxx 选出发选择断 yyy 不选边那么从 yyy 选出发也会选择断 yyy 选边而不断 xxx 不选边。
这就恰好避免了上述问题。这个时候就直接去找和源点联通的点求值和。
这也是《太空飞行计划》没拆点而《方格取数》拆点也可做的原因。
所以拆成互斥状态点时一定要是双向绑定的。
这里就可以扯到入度和出度的匹配应用。
比如每次可以选择两个点将两个点度数 −1-1−1 且不同对操作花费不同让最后将所有点度数成为 000。
当你将点拆成左右部分时xxx 左到 yyy 右流了一定也会 yyy 左到 xxx 右流。这个时候一定会让一个点度数就 −2-2−2。
在网络流图上看似是两种走法但对应回去确实一种操作。
所以这个时候就是左右点和源点/汇点的边上流量限制是度数的一半就与二倍递减相匹配了。
小结Ⅲ
关于分层图题目的暗示往往非常明显。
一般涉及状态不同的拆点时就是在分层图上。
当操作有延迟效应无法一次性完成时单位时间也是分层图。
分层图要注意是否有循环。 链层 像天数这种一直增加的连边通常在相邻两层有些操作可能会一次性跨好多层。 但层数总是不减的。 “出口”往往是从最后一层的点出来。 环层。 像循环的油量补充的分层图是一个循环。 一般这种时候“出口”每一层的出口点都是出口。 感觉说的很杂乱因为这是作者自己刷题掉过的坑然后总结出来的。每个人形成的感觉是无法通过学习他人结果建立的只能自己去试错。——作者 以下是不定期更新
网络流经典模型
网格图的行列匹配(Upd2022-02-15)
例题[ZJOI2007] 矩阵游戏
可以发现如果一开始两个点不在同一行列那么无论怎么交换最后也不会在同一行列。
如果我们把一个 (i,j)1(i,j)1(i,j)1 的点看做是 iii 行 jjj 列的一条匹配边的话。
最后有解的是每一行每一列 (1,1),(2,2),...,(n,n)(1,1),(2,2),...,(n,n)(1,1),(2,2),...,(n,n) 都恰好匹配。
对于原图如果 (i,j)1(i,j)1(i,j)1 就连一条行 i→i\rightarrowi→ 列 jjj 的边。
所有列交换都可以用若干次行交换代替反之亦然。因此我们不妨只考虑行交换。
当按上述规则建立起了一个二分图匹配的网络。
我们交换两行对应的就是交换两个行点对应的列点。
所以如果最后是完备匹配那么一定存在方案将其交换成 iii 行 iii 列的匹配。
明白这一点过后这道题就是个普普通通的匹配问题跑最大流。
#include bits/stdc.h
using namespace std;
#define maxn 1005
#define inf 0x3f3f3f3f
int T, n, s, t, cnt;
int head[maxn], dep[maxn], cur[maxn];
struct node { int to, nxt, flow; }E[maxn * maxn];
queue int q;void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w }, head[u] cnt;E[ cnt] { u, head[v], 0 }, head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to; if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {int v E[i].to; cur[u] i;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, inf );return ans;
}int main() {scanf( %d, T );while( T -- ) {scanf( %d, n );memset( head, -1, sizeof( head ) );cnt -1, s 0, t n 1 | 1;for( int i 1;i n;i ) {for( int j 1, x;j n;j ) {scanf( %d, x );if( x ) addedge( i, j n, inf );}addedge( s, i, 1 );addedge( i n, t, 1 );}if( dinic() n ) puts(Yes);else puts(No);}return 0;
}图的入度出度匹配(Upd2022-02-15)
例题[TJOI2013]循环格
一个循环我们可以看成是一个欧拉回路。题目就是求改边的最小次数可以将一个一般图转化成若干条欧拉回路。
那么每个位置只会存在于一条欧拉回路里面。也就是说这个点的入度和出度是匹配的。
将每个点拆成入度和出度点将四个方向都连边。本身就是这个方向的这条边就不带花费。
否则带花费 111流了这条边就相当于是进行了一次改边操作。
这样就转化成了费用流模型。
还有一道题也是考察的这个一般图带权多重匹配
#include bits/stdc.h
using namespace std;
#define maxn 500
#define inf 0x7f7f7f7f
struct node { int to, nxt, flow, cost; }E[maxn 4];
int n, m, s, t, cnt -1;
char dir[maxn];
int dis[maxn], lst[maxn], vis[maxn], head[maxn];
queue int q;void addedge( int u, int v, int flow, int cost ) {E[ cnt] { v, head[u], flow, cost }, head[u] cnt;E[ cnt] { u, head[v], 0, - cost }, head[v] cnt;
}bool SPFA() {memset( dis, 0x3f, sizeof( dis ) );memset( lst, -1, sizeof( lst ) );dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}int MCMF() {int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i].flow - flow;E[i ^ 1].flow flow;ans flow * E[i].cost;}}return ans;
}int id( int x, int y ) { if( x 1 ) x n;if( x n ) x 1;if( y 1 ) y m;if( y m ) y 1;return (x - 1) * m y;
}int main() {scanf( %d %d, n, m );memset( head, -1, sizeof( head ) );s 0, t n * m 1 | 1;for( int i 1;i n;i ) {scanf( %s, dir 1 );for( int j 1;j m;j ) {addedge( s, id(i, j), 1, 0 );addedge( id(i, j) n * m, t, 1, 0 );addedge( id(i, j), id(i - 1, j) n * m, inf, dir[j] ! U );addedge( id(i, j), id(i 1, j) n * m, inf, dir[j] ! D );addedge( id(i, j), id(i, j - 1) n * m, inf, dir[j] ! L );addedge( id(i, j), id(i, j 1) n * m, inf, dir[j] ! R );}}printf( %d\n, MCMF() );return 0;
}连续区间建图问题
单纯地对二十四题中《最长k可重区间问题》的再阐释。 看第一种解法的详细阐释即可
