seo优化网站优化,计算机网站建设的能力,网站文章不收录怎么办,全球互联网中心在哪里problem
luogu-P3980
solution
志愿者连续工作 [si,ti][s_i,t_i][si,ti] 天#xff0c;我们可以提炼出网络流二十四题中《最长k可重区间集问题》的模型。
同样地#xff0c;把 1∼n1\sim n1∼n 天抽象成一条 1∼n11\sim n11∼n1 个点的链条。
源点 s→1s\rightarrow…problem
luogu-P3980
solution
志愿者连续工作 [si,ti][s_i,t_i][si,ti] 天我们可以提炼出网络流二十四题中《最长k可重区间集问题》的模型。
同样地把 1∼n1\sim n1∼n 天抽象成一条 1∼n11\sim n11∼n1 个点的链条。
源点 s→1s\rightarrow 1s→1 容量无穷费用零n1→tn1\rightarrow tn1→t 汇点 容量无穷费用零。然后 i→i1i\rightarrow i1i→i1 容量 ∞−ai\infty-a_i∞−ai 费用零。对于第 iii 种志愿者si→ti1s_i\rightarrow t_i1si→ti1 容量无穷费用 cic_ici。
最后跑最小费用最大流即为答案。
如果无法直接理解这样建图的正确性可以考虑把网络图中的流量流起来。
如果从 sss 沿着费用零的边向 ttt 流由于链条上的边流量为 ∞−ai\infty-a_i∞−ai所以先前 ∞\infty∞ 的不能流完。
那么势必要通过有志愿者花费的边流。
假设流到了点 iii那么剩下不能流过 (i,i1)(i,i1)(i,i1) 的流量我们得从 iii 连出去的志愿者边流并且流一个就要花费 cic_ici 的代价。
然后在点 x1x1x1 的时候这些流量又会汇合。
这就相当于招募了从 iii 开始到 xxx 结束的志愿者。当然可能有多个 xxx 结束点
反正到最后 ttt 的时候流量总和一定会汇聚成从 sss 开始流的 ∞\infty∞。
你可以理解一队人去闯密室逃脱在一定关卡要进行多人支线任务需要大部队派一些人去完成然后主线队继续往下走主线任务到了一定关卡有些人完成了自己的支线任务可以归队了。最后通关的时候一定是大家都从主线任务关卡口出来。
code
#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 head[maxn], dis[maxn], lst[maxn], vis[maxn], a[maxn];
int cnt -1, n, m, 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 ) );q.push( dis[s] 0 );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;
}signed main() {memset( head, -1, sizeof( head ) );scanf( %lld %lld, n, m );s 0, t n 2;for( int i 1;i n;i ) scanf( %lld, a[i] );for( int i 1;i n;i ) addedge( i, i 1, inf - a[i], 0 );addedge( s, 1, inf, 0 );addedge( n 1, t, inf, 0 );for( int i 1, u, v, w;i m;i ) {scanf( %lld %lld %lld, u, v, w );addedge( u, v 1, inf, w );}printf( %lld\n, MCMF() );return 0;
}solution(流量平衡)
假设共 333 天第 iii 天招募 pip_ipi 人。
共有三类志愿者
从第 111 天工作到第 333 天费用为 c1c_1c1招募了 b1b_1b1 人。从第 222 天工作到第 333 天费用为 c2c_2c2招募了 b2b_2b2 人。从第 111 天工作到第 222 天费用为 c3c_3c3招募了 b3b_3b3 人。
则有以下不等式 {b1b3≥a1b1b2b3≥a2b1b2≥a3\begin{cases} b_1b_3\ge a_1\\b_1b_2b_3\ge a_2\\b_1b_2\ge a_3 \end{cases} ⎩⎪⎨⎪⎧b1b3≥a1b1b2b3≥a2b1b2≥a3 记第 iii 天招募的志愿者超出最少要求人数 did_idi 人显然 di≥0d_i\ge 0di≥0。则可改写成以下等式 {p1b1b3a1d1p2b1b2b3a2d2p3b1b2a3d3\begin{cases}p_1b_1b_3a_1d_1\\p_2b_1b_2b_3a_2d_2\\p_3b_1b_2a_3d_3\end{cases} ⎩⎪⎨⎪⎧p1b1b3a1d1p2b1b2b3a2d2p3b1b2a3d3 将相邻两两等式作差后移项整理得 {p1b1b3a1d1p2−p1b2−b3a2−a1d2−d1p3−p2−b3a3−a2d3−d2−p3−b1−b2−a3−d3⇒{p1−p0b1b3−a1−d10p2−p1b2−b3−a2a1−d2d10p3−p2−b3−a3a2−d3d20p4−p3−b1−b2a3d30\begin{cases}p_1b_1b_3a_1d_1\\p_2-p_1b_2-b_3a_2-a_1d_2-d_1\\ p_3-p_2-b_3a_3-a_2d_3-d_2\\-p_3-b_1-b_2-a_3-d_3\end{cases}\Rightarrow \begin{cases}p_1-p_0b_1b_3-a_1-d_10\\p_2-p_1b_2-b_3-a_2a_1-d_2d_10\\ p_3-p_2-b_3-a_3a_2-d_3d_20\\p_4-p_3-b_1-b_2a_3d_30 \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧p1b1b3a1d1p2−p1b2−b3a2−a1d2−d1p3−p2−b3a3−a2d3−d2−p3−b1−b2−a3−d3⇒⎩⎪⎪⎪⎨⎪⎪⎪⎧p1−p0b1b3−a1−d10p2−p1b2−b3−a2a1−d2d10p3−p2−b3−a3a2−d3d20p4−p3−b1−b2a3d30 网络流中除了源汇点其余点都应满足流量平衡即流入流量等于流出流量若将流入记为正流出记为负则应满足流入流出流量的代数和为 000。
网络图中一条连接 x,yx,yx,y 的边在 x,yx,yx,y 的流量平衡等式中各出现一次且一次为正一次为负。
所以我们可以对上面最后化出的等式每个建立一个点这个等式表示的就是这个点流量平衡。
再观察最后的等式
observationⅠ.\text{observationⅠ.}observationⅠ. bi,dib_i,d_ibi,di 都在恰好两个等式出现且是一正一负。所以每一个变量 bi,dib_i,d_ibi,di 都可以作为网络图中的一条边。
observationⅡ.\text{observationⅡ.}observationⅡ. 常量 aia_iai 也恰好在两个等式中出现且是一正一负。为正时表示流入可以和源点连边为负时表示流出可以和汇点连边。
根据作差规则aia_iai 一定是出现在第 i,i1i,i1i,i1 两个等式中且一定第 iii 个等式为负第 i1i1i1 个为正。
常量与源汇点连边变量表示常量点之间的边跑平衡。
最后答案是 min∑bi⋅ci\min \sum b_i·c_imin∑bi⋅ci 可以以“费用”的形式表示出来。 简述建图方式 假设 a0an10a_0a_{n1}0a0an10。 建立源汇点 s,ts,ts,t。建立点 1∼n11\sim n11∼n1代表 n1n1n1 个等式。第 i1i1i1 个点向第 iii 个点连一条容量无穷费用为零的边。对应 bi,dib_i,d_ibi,di 的平衡。第 iii 类志愿者连边 si→ti1s_i\rightarrow t_i1si→ti1容量无穷费用为 cic_ici。对于第 iii 个点若 ai−ai−1a_i-a_{i-1}ai−ai−1 为正连边 s→is\rightarrow is→i容量 ai−ai−1a_i-a_{i-1}ai−ai−1 费用为零若为负连边 i→ti\rightarrow ti→t容量 ai−1−aia_{i-1}-a_iai−1−ai 费用为零。相当于等式中的常数项。
实际理解上可以把常数项提到右边 {b1b3−d1a1−a0b2−b3−d2d1a2−a1−b3−d3d2a3−a2−b1−b2d3a4−a3\begin{cases} b_1b_3-d_1a_1-a_0\\ b_2-b_3-d_2d_1a_2-a_1\\ -b_3-d_3d_2a_3-a_2\\ -b_1-b_2d_3a_4-a_3 \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧b1b3−d1a1−a0b2−b3−d2d1a2−a1−b3−d3d2a3−a2−b1−b2d3a4−a3 把 ai−ai−1a_i-a_{i-1}ai−ai−1 当成第 iii 个等式的盈亏量这样你就能理解正负与源汇连边的意义了。
code
#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 head[maxn], dis[maxn], lst[maxn], vis[maxn], a[maxn];
int cnt -1, n, m, 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 ) );q.push( dis[s] 0 );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;
}signed main() {memset( head, -1, sizeof( head ) );scanf( %lld %lld, n, m );s 0, t n 2;for( int i 1;i n;i ) scanf( %lld, a[i] );for( int i 1;i n;i ) addedge( i 1, i, inf, 0 );for( int i 1, u, v, w;i m;i ) {scanf( %lld %lld %lld, u, v, w );addedge( u, v 1, inf, w );}for( int i 1;i n 1;i )if( a[i] - a[i - 1] 0 ) addedge( s, i, a[i] - a[i - 1], 0 );else addedge( i, t, a[i - 1] - a[i], 0 );printf( %lld\n, MCMF() );return 0;
}其实流量平衡的建边含义理解还有从线性规划对偶角度出发的。会在《防守战线》中详细说明。
