CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » jxm2001 » 图论_3
2020-2021:teams:legal_string:jxm2001:图论_3

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:legal_string:jxm2001:图论_3 [2020/07/21 16:28]
jxm2001 		2020-2021:teams:legal_string:jxm2001:图论_3 [2020/07/27 22:59] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:图论_3被移动至2020-2021:teams:legal_string:jxm2001:图论_3
行 33: 行 33:
 最后从黑格向有冲突的白格连一条边，容量待定。 最后从黑格向有冲突的白格连一条边，容量待定。
  
-问题转化为最小割问题，事实上图不连通等价于没有从源点到黑格，黑格经过冲突边到白格，白格再到汇点的路径。+问题转化为最小割问题。 
 + 
 +事实上网络流图不连通等价于没有从源点到黑格，再经过冲突边到白格，最后到汇点的路径。
  
 这又等价于不会同时选择冲突的黑格和白格，即最终的目的。 这又等价于不会同时选择冲突的黑格和白格，即最终的目的。
行 43: 行 45:
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
-#include <​iostream>​ 
-#include <​cstdio>​ 
-#include <​cstdlib>​ 
-#include <​algorithm>​ 
-#include <​string>​ 
-#include <​sstream>​ 
-#include <​cstring>​ 
-#include <​cctype>​ 
-#include <​cmath>​ 
-#include <​vector>​ 
-#include <set> 
-#include <map> 
-#include <​stack>​ 
-#include <​queue>​ 
-#include <​ctime>​ 
-#include <​cassert>​ 
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) 
-#define _rep(i,a,b) for(int i=(a);​i<​=(b);​++i) 
-#define mem(a,b) memset(a,​b,​sizeof(a)) 
-using namespace std; 
-typedef long long LL; 
-inline int read_int(){ 
- int t=0;bool sign=false;​char c=getchar();​ 
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} 
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} 
- return sign?-t:t; 
-} 
-inline LL read_LL(){ 
- LL t=0;bool sign=false;​char c=getchar();​ 
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} 
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} 
- return sign?-t:t; 
-} 
-inline char get_char(){ 
- char c=getchar();​ 
- while(c=='​ '​||c=='​\n'​||c=='​\r'​)c=getchar();​ 
- return c; 
-} 
-inline void write(LL x){ 
- register char c[21],​len=0;​ 
- if(!x)return putchar('​0'​),​void();​ 
- if(x<​0)x=-x,​putchar('​-'​);​ 
- while(x)c[++len]=x%10,​x/​=10;​ 
- while(len)putchar(c[len--]+48);​ 
-} 
-inline void space(LL x){write(x),​putchar('​ ');} 
-inline void enter(LL x){write(x),​putchar('​\n'​);​} 
 const int MAXS=105,​MAXN=MAXS*MAXS,​MAXM=6*MAXN,​Inf=0x7fffffff;​ const int MAXS=105,​MAXN=MAXS*MAXS,​MAXM=6*MAXN,​Inf=0x7fffffff;​
 const int dir[][2]={{0,​1},​{0,​-1},​{1,​0},​{-1,​0}};​ const int dir[][2]={{0,​1},​{0,​-1},​{1,​0},​{-1,​0}};​
行 186: 行 141:
 </​hidden>​ </​hidden>​
  
-====  ​航空路线问题 ====+=== 练习题 === 
 + 
 +[[https://​www.luogu.com.cn/​problem/​P2762|洛谷p2762]] 
 + 
 +== 题意 == 
 + 
 +给定 $n$ 个可选择实验，$m$ 个实验器材。完成第 $i$ 个实验可以得到 $p_i$ 元奖金，购买第 $j$ 个实验器材需要花费 $c_j$ 元。 
 + 
 +完成每个实验需要若干个器材(允许多个实验共用一个器材)，问最大利益及购买方案。 
 + 
 +== 题解 == 
 + 
 +先收取所有实验的奖金。然后考虑要么舍弃实验奖金，要么购买相应器材。 
 + 
 +剩下思路类似方格取数。 
 + 
 +<hidden 查看代码>​ 
 +<code cpp> 
 +const int MAXN=200,​MAXM=3000,​Inf=0x7fffffff;​ 
 +struct Edge{ 
 + int to,​cap,​next;​ 
 + Edge(int to=0,int cap=0,int next=0){ 
 + this->​to=to;​ 
 + this->​cap=cap;​ 
 + this->​next=next;​ 
 + } 
 +}edge[MAXM<<​1];​ 
 +int head[MAXN],​edge_cnt;​ 
 +void Clear(){mem(head,​-1);​edge_cnt=0;​}//​边从0开始编号  
 +void Insert(int u,int v,int c){ 
 + edge[edge_cnt]=Edge(v,​c,​head[u]);​ 
 + head[u]=edge_cnt++;​ 
 + edge[edge_cnt]=Edge(u,​0,​head[v]);​ 
 + head[v]=edge_cnt++;​ 
 +} 
 +struct Dinic{ 
 + int s,t; 
 + int pos[MAXN],​vis[MAXN],​dis[MAXN];​ 
 + bool bfs(int k){ 
 + queue<​int>​q;​ 
 + q.push(s);​ 
 + vis[s]=k,​dis[s]=0,​pos[s]=head[s];​ 
 + while(!q.empty()){ 
 + int u=q.front();​q.pop();​ 
 + for(int i=head[u];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(vis[v]!=k&&​edge[i].cap){ 
 + vis[v]=k,​dis[v]=dis[u]+1,​pos[v]=head[v];​ 
 + q.push(v);​ 
 + if(v==t) 
 + return true; 
 + } 
 + } 
 + } 
 + return false; 
 + } 
 + int dfs(int u,int max_flow){ 
 + if(u==t||!max_flow) 
 + return max_flow; 
 + int flow=0,​temp_flow;​ 
 + for(int &​i=pos[u];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(dis[u]+1==dis[v]&&​(temp_flow=dfs(v,​min(max_flow,​edge[i].cap)))){ 
 + edge[i].cap-=temp_flow;​ 
 + edge[i^1].cap+=temp_flow;​ 
 + flow+=temp_flow;​ 
 + max_flow-=temp_flow;​ 
 + if(!max_flow) 
 + break;​ 
 + } 
 + } 
 + return flow; 
 + } 
 + int Maxflow(int s,int t){ 
 + this->​s=s;​this->​t=t;​ 
 + int ans=0,​k=0;​ 
 + mem(vis,​0);​ 
 + while(bfs(++k)) 
 + ans+=dfs(s,​Inf);​ 
 + return ans; 
 + } 
 +}solver; 
 +char buf[MAXN];​ 
 +bool vis[MAXN];​ 
 +void dfs(int u){ 
 + vis[u]=true;​ 
 + for(int i=head[u];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(vis[v]||edge[i].cap==0) 
 + continue;​ 
 + dfs(v); 
 + } 
 +} 
 +int main() 
 +{ 
 + Clear(); 
 + int n=read_int(),​m=read_int(),​s=n+m+1,​t=s+1;​ 
 + int c,​pos,​p,​sum=0;​ 
 + _rep(i,​1,​n){ 
 + sum+=c=read_int();​ 
 + Insert(s,​i,​c);​ 
 + gets(buf);​ 
 + pos=0; 
 + while(sscanf(buf+pos,"​%d",&​p)==1){ 
 + Insert(i,​p+n,​Inf);​ 
 + if(p==0) 
 + pos++; 
 + else{ 
 + while(p){ 
 + p/​=10;​ 
 + pos++;​ 
 + } 
 + } 
 + while(buf[pos]=='​ ') 
 + pos++; 
 + } 
 + } 
 + _rep(i,​1,​m) 
 + Insert(i+n,​t,​read_int());​ 
 + int flow=solver.Maxflow(s,​t);​ 
 + dfs(s); 
 + _rep(i,​1,​n) if(vis[i]) 
 + space(i);​ 
 + puts(""​);​ 
 + _rep(i,​1,​m) if(vis[i+n]) 
 + space(i);​ 
 + puts(""​);​ 
 + enter(sum-flow);​ 
 + return 0; 
 +} 
 +</​code>​ 
 +</​hidden>​ 
 + 
 +=== 最大权闭合子图 === 
 + 
 +== 定义 == 
 + 
 +给定一个有向图，取图中的一些点构成点集 $V$，若对 $V$ 中的任意一个节点其后继节点均属于 $V$，则称 $V$ 及其相关边为闭合子图。 
 + 
 +如果每个点拥有一个点权，则称 $V$ 点权和最大的闭合子图为最大权闭合子图。 
 + 
 +== 性质 == 
 + 
 +按如下规则构图： 
 +  * 若某点点权为正，则从源点连一条容量等于点权的边到该点 
 +  * 若某点点权为负，则从该点连一条容量等于点权绝对值的边到汇点 
 +  * 如某条边属于原图，则将其容量改为 $\inf$ 
 +在该图中跑最大流，则最大权闭合子图点权和 $=$ 所有正点权之和 $-$ 最小割。 
 + 
 +== 证明 == 
 + 
 +简单割定义：割 $(S,T)$ 中每一条割边都与 $s$ 或者 $t$ 相连。 
 + 
 +**任意闭合子图一定对应一个简单割**，否则取闭合子图和源点构成 $S$，其余点构成 $T$。 
 + 
 +如果有 $(u,​v)\subset E,u\in S,v\in T$，则表示选择 $u$但不选择 $v$，与闭合子图定义矛盾。 
 + 
 +**任意一个简单割对应一个闭合子图**，因为对 $(u,​v)\subset E,u\in S$，根据简单割定义，有 $v\in S$，满足闭合子图定义。 
 + 
 +记 $T$ 中所有正权点的权值之和为 $T_1$，$S$ 中所有正权点的权值之和为 $S_1$，$T$ 中所有负权点的权值绝对值之和为 $S_2$。 
 + 
 +则割的容量 $C(S,​T)=T_1+S_2$，闭合子图的权值 $W=S_1-S_2$。 
 + 
 +则有 $C(S,​T)+W=T_1+S_1$，即 $W=T_1+S_1-C(S,​T)$。 
 + 
 +$T_1+S_1$ 即为所有正点权之和，是定值。剩下只需要考虑令 $C(S,T)$ 尽量小。 
 + 
 +而按上述方法构建的网络流图的最小割一定为简单割，因为非简单割容量大于 $\inf$，一定不是最小割。 
 + 
 +所以直接求最小割即可，证毕。 
 + 
 +====  最小路径覆盖问题 ==== 
 + 
 +[[https://​www.luogu.com.cn/​problem/​P2764|洛谷p2764]] 
 + 
 +=== 题意 === 
 + 
 +给定一个 $\text{DAG}$，求最小的不相交路径集，使得每个点恰好属于其中一条路径。(允许路径长度为 $0$，此时路径仅覆盖一个点) 
 + 
 +=== 题解 === 
 + 
 +先用 $n$ 条长度为 $0$ 的路径覆盖 $n$ 个点，然后考虑合并路径。 
 + 
 +将每个点拆成入点和出点，易知每个入点/​出点最多被合并一次，否则有两条路径相交。 
 + 
 +从源点连一条容量为 $1$ 的边到每个入点，从每个出点连一条容量为 $1$ 的边到汇点，则可以满足上述的合并次数限制。 
 + 
 +最后，对每条边，从入点连一条容量为 $1$ 的边到出点，表示以入点结束的路径可与以出点开始的路径合并一次。 
 + 
 +最后需要合并次数最多，跑最大流即可。最小路径覆盖为节点数减去最大流。 
 + 
 +关于路径打印，只要在求完最大流后跑残量网络即可。 
 + 
 +<hidden 查看代码>​ 
 +<code cpp> 
 +const int MAXN=305,​MAXM=18005,​Inf=0x7fffffff;​ 
 +struct Edge{ 
 + int to,​cap,​next;​ 
 + Edge(int to=0,int cap=0,int next=0){ 
 + this->​to=to;​ 
 + this->​cap=cap;​ 
 + this->​next=next;​ 
 + } 
 +}edge[MAXM<<​1];​ 
 +int head[MAXN],​edge_cnt;​ 
 +void Clear(){mem(head,​-1);​edge_cnt=0;​}//​边从0开始编号  
 +void Insert(int u,int v,int c){ 
 + edge[edge_cnt]=Edge(v,​c,​head[u]);​ 
 + head[u]=edge_cnt++;​ 
 + edge[edge_cnt]=Edge(u,​0,​head[v]);​ 
 + head[v]=edge_cnt++;​ 
 +} 
 +struct Dinic{ 
 + int s,t; 
 + int pos[MAXN],​vis[MAXN],​dis[MAXN];​ 
 + bool bfs(int k){ 
 + queue<​int>​q;​ 
 + q.push(s);​ 
 + vis[s]=k,​dis[s]=0,​pos[s]=head[s];​ 
 + while(!q.empty()){ 
 + int u=q.front();​q.pop();​ 
 + for(int i=head[u];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(vis[v]!=k&&​edge[i].cap){ 
 + vis[v]=k,​dis[v]=dis[u]+1,​pos[v]=head[v];​ 
 + q.push(v);​ 
 + if(v==t) 
 + return true; 
 + } 
 + } 
 + } 
 + return false; 
 + } 
 + int dfs(int u,int max_flow){ 
 + if(u==t||!max_flow) 
 + return max_flow; 
 + int flow=0,​temp_flow;​ 
 + for(int &​i=pos[u];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(dis[u]+1==dis[v]&&​(temp_flow=dfs(v,​min(max_flow,​edge[i].cap)))){ 
 + edge[i].cap-=temp_flow;​ 
 + edge[i^1].cap+=temp_flow;​ 
 + flow+=temp_flow;​ 
 + max_flow-=temp_flow;​ 
 + if(!max_flow) 
 + break;​ 
 + } 
 + } 
 + return flow; 
 + } 
 + int Maxflow(int s,int t){ 
 + this->​s=s;​this->​t=t;​ 
 + int ans=0,​k=0;​ 
 + mem(vis,​0);​ 
 + while(bfs(++k)) 
 + ans+=dfs(s,​Inf);​ 
 + return ans; 
 + } 
 +}solver; 
 +int Next[MAXN],​Pre[MAXN];​ 
 +int main() 
 +{ 
 + int n=read_int(),​m=read_int(),​u,​v;​ 
 + int s=2*n+1,​t=2*n+2;​ 
 + Clear(); 
 + _rep(i,​1,​n){ 
 + Insert(s,​i,​1);​ 
 + Insert(i+n,​t,​1);​ 
 + } 
 + while(m--){ 
 + u=read_int(),​v=read_int();​ 
 + Insert(u,​v+n,​1);​ 
 + } 
 + int flow=solver.Maxflow(s,​t);​ 
 + _rep(u,​1,​n){ 
 + for(int i=head[u];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(v!=s&&​edge[i].cap==0){ 
 + Next[u]=v-n;​ 
 + Pre[v-n]=u;​ 
 + } 
 + } 
 + } 
 + _rep(i,​1,​n){ 
 + if(!Pre[i]){ 
 + int pos=i; 
 + while(pos){ 
 + space(pos);​ 
 + pos=Next[pos];​ 
 + } 
 + puts(""​);​ 
 + } 
 + } 
 + enter(n-flow);​ 
 + return 0; 
 +} 
 +</​code>​ 
 +</​hidden>​ 
 + 
 +=== 练习题 === 
 + 
 +[[https://​www.luogu.com.cn/​problem/​P2765|洛谷p2765]] 
 + 
 +== 题意 == 
 + 
 +给定 $n$ 个栈，要求依次放入 $1,​2,​3,​\cdots$ 
 + 
 +要求同一个栈中每两个相邻元素之和是平方数。 
 + 
 +输出最多可以放入的数的个数以及任意一个方案。 
 + 
 +== 题解 == 
 + 
 +把原图想像成一个 $\text{DAG}$，小数向可以与它相加构成平方数的大数连一条单向边，需要栈的个数等于最小路径覆盖。 
 + 
 +依次向图中加入每个数，每次加入一个数时先用长度为 $0$ 的路径将其覆盖，然后在残量网络中考虑路径合并。 
 + 
 +残量网络流量为 $0$ 表示路径合并失败，需要使用一个新的栈。如果最小路径覆盖不超过 $n$ 即可继续加数，否则终止循环。 
 + 
 +方案打印同最小路径覆盖。 
 + 
 +<hidden 查看代码>​ 
 +<code cpp> 
 +const int MAXN=1e5+5,​MAXM=2e5+5,​Inf=0x7fffffff;​ 
 +struct Edge{ 
 + int to,​cap,​next;​ 
 + Edge(int to=0,int cap=0,int next=0){ 
 + this->​to=to;​ 
 + this->​cap=cap;​ 
 + this->​next=next;​ 
 + } 
 +}edge[MAXM<<​1];​ 
 +int head[MAXN],​edge_cnt;​ 
 +void Clear(){mem(head,​-1);​edge_cnt=0;​}//​边从0开始编号  
 +void Insert(int u,int v,int c){ 
 + edge[edge_cnt]=Edge(v,​c,​head[u]);​ 
 + head[u]=edge_cnt++;​ 
 + edge[edge_cnt]=Edge(u,​0,​head[v]);​ 
 + head[v]=edge_cnt++;​ 
 +} 
 +struct Dinic{ 
 + int s,t; 
 + int pos[MAXN],​vis[MAXN],​dis[MAXN];​ 
 + bool bfs(int k){ 
 + queue<​int>​q;​ 
 + q.push(s);​ 
 + vis[s]=k,​dis[s]=0,​pos[s]=head[s];​ 
 + while(!q.empty()){ 
 + int u=q.front();​q.pop();​ 
 + for(int i=head[u];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(vis[v]!=k&&​edge[i].cap){ 
 + vis[v]=k,​dis[v]=dis[u]+1,​pos[v]=head[v];​ 
 + q.push(v);​ 
 + if(v==t) 
 + return true; 
 + } 
 + } 
 + } 
 + return false; 
 + } 
 + int dfs(int u,int max_flow){ 
 + if(u==t||!max_flow) 
 + return max_flow; 
 + int flow=0,​temp_flow;​ 
 + for(int &​i=pos[u];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(dis[u]+1==dis[v]&&​(temp_flow=dfs(v,​min(max_flow,​edge[i].cap)))){ 
 + edge[i].cap-=temp_flow;​ 
 + edge[i^1].cap+=temp_flow;​ 
 + flow+=temp_flow;​ 
 + max_flow-=temp_flow;​ 
 + if(!max_flow) 
 + break;​ 
 + } 
 + } 
 + return flow; 
 + } 
 + int Maxflow(int s,int t){ 
 + this->​s=s;​this->​t=t;​ 
 + int ans=0,​k=0;​ 
 + mem(vis,​0);​ 
 + while(bfs(++k)) 
 + ans+=dfs(s,​Inf);​ 
 + return ans; 
 + } 
 +}solver; 
 +const int MAXS=60; 
 +int Next[MAXN],​Pre[MAXN],​s=MAXN-2,​t=MAXN-1;​ 
 +int main() 
 +{ 
 + Clear(); 
 + int n=read_int(),​pos=0,​num=0;​ 
 + while(pos<​=n){ 
 + ++num; 
 + Insert(s,​num<<​1,​1);​Insert(num<<​1|1,​t,​1);​ 
 + for(int i=sqrt(num)+1;​i*i<​2*num;​i++) 
 + Insert((i*i-num)<<​1,​num<<​1|1,​1);​ 
 + if(solver.Maxflow(s,​t)==0) 
 + pos++; 
 + } 
 + enter(--num);​ 
 + _rep(u,​1,​num){ 
 + for(int i=head[u<<​1];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(v!=s&&​edge[i].cap==0){ 
 + Next[u]=v>>​1;​ 
 + Pre[v>>​1]=u;​ 
 + } 
 + } 
 + } 
 + _rep(i,​1,​num){ 
 + if(!Pre[i]){ 
 + int pos=i; 
 + while(pos){ 
 + space(pos);​ 
 + pos=Next[pos];​ 
 + } 
 + puts(""​);​ 
 + } 
 + } 
 + return 0; 
 +} 
 +</​code>​ 
 +</​hidden>​ 
 + 
 +====  ​往返路线问题 ====
  
 [[https://​www.luogu.com.cn/​problem/​P2770|洛谷p2770]] [[https://​www.luogu.com.cn/​problem/​P2770|洛谷p2770]]
行 213: 行 594:
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
-#include <​iostream>​ 
-#include <​cstdio>​ 
-#include <​cstdlib>​ 
-#include <​algorithm>​ 
-#include <​string>​ 
-#include <​sstream>​ 
-#include <​cstring>​ 
-#include <​cctype>​ 
-#include <​cmath>​ 
-#include <​vector>​ 
-#include <set> 
-#include <map> 
-#include <​stack>​ 
-#include <​queue>​ 
-#include <​ctime>​ 
-#include <​cassert>​ 
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) 
-#define _rep(i,a,b) for(int i=(a);​i<​=(b);​++i) 
-#define mem(a,b) memset(a,​b,​sizeof(a)) 
-using namespace std; 
-typedef long long LL; 
-inline int read_int(){ 
- int t=0;bool sign=false;​char c=getchar();​ 
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} 
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} 
- return sign?-t:t; 
-} 
-inline LL read_LL(){ 
- LL t=0;bool sign=false;​char c=getchar();​ 
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} 
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} 
- return sign?-t:t; 
-} 
-inline char get_char(){ 
- char c=getchar();​ 
- while(c=='​ '​||c=='​\n'​||c=='​\r'​)c=getchar();​ 
- return c; 
-} 
-inline void write(LL x){ 
- register char c[21],​len=0;​ 
- if(!x)return putchar('​0'​),​void();​ 
- if(x<​0)x=-x,​putchar('​-'​);​ 
- while(x)c[++len]=x%10,​x/​=10;​ 
- while(len)putchar(c[len--]+48);​ 
-} 
-inline void space(LL x){write(x),​putchar('​ ');} 
-inline void enter(LL x){write(x),​putchar('​\n'​);​} 
 const int MAXN=205,​MAXM=6000,​Inf=0x7fffffff;​ const int MAXN=205,​MAXM=6000,​Inf=0x7fffffff;​
 struct Edge{ struct Edge{
行 400: 行 734:
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
-#include <​iostream>​ 
-#include <​cstdio>​ 
-#include <​cstdlib>​ 
-#include <​algorithm>​ 
-#include <​string>​ 
-#include <​sstream>​ 
-#include <​cstring>​ 
-#include <​cctype>​ 
-#include <​cmath>​ 
-#include <​vector>​ 
-#include <set> 
-#include <map> 
-#include <​stack>​ 
-#include <​queue>​ 
-#include <​ctime>​ 
-#include <​cassert>​ 
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) 
-#define _rep(i,a,b) for(int i=(a);​i<​=(b);​++i) 
-#define mem(a,b) memset(a,​b,​sizeof(a)) 
-using namespace std; 
-typedef long long LL; 
-inline int read_int(){ 
- int t=0;bool sign=false;​char c=getchar();​ 
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} 
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} 
- return sign?-t:t; 
-} 
-inline LL read_LL(){ 
- LL t=0;bool sign=false;​char c=getchar();​ 
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} 
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} 
- return sign?-t:t; 
-} 
-inline char get_char(){ 
- char c=getchar();​ 
- while(c=='​ '​||c=='​\n'​||c=='​\r'​)c=getchar();​ 
- return c; 
-} 
-inline void write(LL x){ 
- register char c[21],​len=0;​ 
- if(!x)return putchar('​0'​),​void();​ 
- if(x<​0)x=-x,​putchar('​-'​);​ 
- while(x)c[++len]=x%10,​x/​=10;​ 
- while(len)putchar(c[len--]+48);​ 
-} 
-inline void space(LL x){write(x),​putchar('​ ');} 
-inline void enter(LL x){write(x),​putchar('​\n'​);​} 
 const int MAXN=105,​MAXM=6000;​ const int MAXN=105,​MAXM=6000;​
 struct Edge{ struct Edge{
行 560: 行 847:
  
 对每个区间，仍然按上述方案连边。最后从源点连一条容量为 $k$ 的边到最左端点，从最右端点连一条容量为 $k$ 的边到汇点，跑费用流即可。 对每个区间，仍然按上述方案连边。最后从源点连一条容量为 $k$ 的边到最左端点，从最右端点连一条容量为 $k$ 的边到汇点，跑费用流即可。
 +
 +如果题目把开区间改成闭区间，拆点的时候当作 $[lef,​rig+1)$ 处理就行。
  
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
-#include <​iostream>​ 
-#include <​cstdio>​ 
-#include <​cstdlib>​ 
-#include <​algorithm>​ 
-#include <​string>​ 
-#include <​sstream>​ 
-#include <​cstring>​ 
-#include <​cctype>​ 
-#include <​cmath>​ 
-#include <​vector>​ 
-#include <set> 
-#include <map> 
-#include <​stack>​ 
-#include <​queue>​ 
-#include <​ctime>​ 
-#include <​cassert>​ 
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) 
-#define _rep(i,a,b) for(int i=(a);​i<​=(b);​++i) 
-#define mem(a,b) memset(a,​b,​sizeof(a)) 
-using namespace std; 
-typedef long long LL; 
-inline int read_int(){ 
- int t=0;bool sign=false;​char c=getchar();​ 
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} 
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} 
- return sign?-t:t; 
-} 
-inline LL read_LL(){ 
- LL t=0;bool sign=false;​char c=getchar();​ 
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} 
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} 
- return sign?-t:t; 
-} 
-inline char get_char(){ 
- char c=getchar();​ 
- while(c=='​ '​||c=='​\n'​||c=='​\r'​)c=getchar();​ 
- return c; 
-} 
-inline void write(LL x){ 
- register char c[21],​len=0;​ 
- if(!x)return putchar('​0'​),​void();​ 
- if(x<​0)x=-x,​putchar('​-'​);​ 
- while(x)c[++len]=x%10,​x/​=10;​ 
- while(len)putchar(c[len--]+48);​ 
-} 
-inline void space(LL x){write(x),​putchar('​ ');} 
-inline void enter(LL x){write(x),​putchar('​\n'​);​} 
 const int MAXN=1005,​MAXM=2005,​Inf=0x7fffffff;​ const int MAXN=1005,​MAXM=2005,​Inf=0x7fffffff;​
 struct Edge{ struct Edge{
行 712: 行 954:
 </​hidden>​ </​hidden>​
  
-=== 拓展 ​===+====  最长不下降子序列问题 ====
  
-如果题目把开区间改成闭区间，拆点的时候当作 $[lef,​rig+1)$ 处理就行。 +[[https://​www.luogu.com.cn/​problem/​P2766|洛谷p2766]]
- +
-====  最小路径覆盖问题 ==== +
- +
-[[https://​www.luogu.com.cn/​problem/​P2764|洛谷p2764]]+
  
 === 题意 === === 题意 ===
  
-给定一个 $\text{DAG}$，求最小的不相交路径集，使得每个点恰好属于其中一条路径。(允许路径长度为 $0$，此时路径仅覆盖一个点)+给定一个正整数序列 ​$x_1,x_2,\cdots x_n$。 
 + 
 +  - 计算其最长不下降子序列的长度 $s$ 
 +  - 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列 
 +  - 如果允许在取出的序列中多次使用 $x_1,x_n$，则从给定序列中最多可取出多少个不同的长度为的 $s$ 不下降子序列
  
 === 题解 === === 题解 ===
  
-先用 ​$n$ 条长度为 ​$0$ 的路径覆盖 $n$ 个点，然后考虑合并路径。+第一问考虑 ​$\text{dp}$ 求出以第 ​$i$ 个数结尾的最长序列长度。
  
-将每个点拆成入点和出点，易知每个入点/​出点最多被合并一次，否则有两条路径相交。+第二问先考虑只允许使用一次这个限制条件，只需要把每个点拆成入点和出点，然后连一条容量为 $1$ 的边即可。
  
-从源点连一条容量为 ​$1$ 的边到每个入点，从每个出点连一条容量为 $1$ 的边到汇点，则可以满足上述的合并次数限制。+接下若满足 ​$j\lt i,a_j\le a_i,​\text{dp}_j+1==\text{dp}_i$，则连一条 ​$j\to i$ 的容量为 $1$ 的边。
  
-最后，对每条边，从入点连一条容量为 $1$ 的边到出点，表示以入点结束的路径可与以出点开始的路径合并一次。+最后考虑从源点向 $\text{dp}_i==1$ 的点连一条容量为 $1$ 的边，从 $\text{dp}_i==s$ ​的点向汇点连一条容量为 $1$ 的边。
  
-最后需要合并次数最多，跑最大流即可。最小路径覆盖为节点数减去最大流。+最后跑最大流即可求出第二问答案。
  
-关于路径打印，只要在求完最大流后跑残量网络即可。+对第三问，考虑把第 $1,n$ 个点的入点和出点的连边容量改为 ​ $\inf$，同时把从源点到第 $1$ 个的连边的容量改为 $\inf$。 
 + 
 +如果 $\text{dp}_n==s$，还需要把从第 $n$ 个点向汇点的连边的容量改为 $\inf$，然后重新跑一遍最大流。 
 + 
 +但实际编程中不需要修改边，额外添加边即可。同时也不需要重新跑最大流，在残量网络上跑最大流然后累加上第二问答案即可。 
 + 
 +需要注意 $s=1$ 的特例，题目需要求不同的不下降子序列就是为了防止此时答案为 $\inf$ 的情况。
  
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
-#include <​iostream>​ +const int MAXN=1005,MAXM=5e5+5,​Inf=0x7fffffff;​
-#include <​cstdio>​ +
-#include <​cstdlib>​ +
-#include <​algorithm>​ +
-#include <​string>​ +
-#include <​sstream>​ +
-#include <​cstring>​ +
-#include <​cctype>​ +
-#include <​cmath>​ +
-#include <​vector>​ +
-#include <​set>​ +
-#include <​map>​ +
-#include <​stack>​ +
-#include <​queue>​ +
-#include <​ctime>​ +
-#include <​cassert>​ +
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) +
-#define _rep(i,a,b) for(int i=(a);​i<​=(b);​++i) +
-#define mem(a,b) memset(a,​b,​sizeof(a)) +
-using namespace std; +
-typedef long long LL; +
-inline int read_int(){ +
- int t=0;bool sign=false;​char c=getchar();​ +
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
- return sign?​-t:​t;​ +
-} +
-inline LL read_LL(){ +
- LL t=0;bool sign=false;​char c=getchar();​ +
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
- return sign?​-t:​t;​ +
-} +
-inline char get_char(){ +
- char c=getchar();​ +
- while(c=='​ '​||c=='​\n'​||c=='​\r'​)c=getchar();​ +
- return c; +
-} +
-inline void write(LL x){ +
- register char c[21],​len=0;​ +
- if(!x)return putchar('​0'​),​void();​ +
- if(x<​0)x=-x,​putchar('​-'​);​ +
- while(x)c[++len]=x%10,​x/​=10;​ +
- while(len)putchar(c[len--]+48);​ +
-} +
-inline void space(LL x){write(x),​putchar('​ ');} +
-inline void enter(LL x){write(x),​putchar('​\n'​);​} +
-const int MAXN=305,MAXM=18005,​Inf=0x7fffffff;​+
 struct Edge{ struct Edge{
  int to,​cap,​next;​  int to,​cap,​next;​
行 851: 行 1052:
  }  }
 }solver; }solver;
-int Next[MAXN],Pre[MAXN];+int a[MAXN],dp[MAXN],​f[MAXN],​pos;
 int main() int main()
 { {
- int n=read_int(),​m=read_int(),​u,v;+ int n=read_int(); 
 + _rep(i,1,n) 
 + a[i]=read_int(); 
 + f[pos=0]=-Inf;​ 
 + _rep(i,1,n){ 
 + if(a[i]>​=f[pos]){ 
 + f[++pos]=a[i];​ 
 + dp[i]=pos;​ 
 + } 
 + else{ 
 + int t=upper_bound(f,​f+pos+1,​a[i])-f;​ 
 + f[t]=a[i];​ 
 + dp[i]=t;​ 
 + } 
 + } 
 + enter(pos);​ 
 + if(pos==1){ 
 + sort(a+1,​a+n+1);​ 
 + int ans=unique(a+1,​a+n+1)-a-1;​ 
 + enter(ans);​ 
 + enter(ans);​ 
 + return 0; 
 + }
  int s=2*n+1,​t=2*n+2;​  int s=2*n+1,​t=2*n+2;​
  Clear();  Clear();
  _rep(i,​1,​n){  _rep(i,​1,​n){
 + Insert(i,​i+n,​1);​
 + if(dp[i]==1)
  Insert(s,​i,​1);​  Insert(s,​i,​1);​
 + if(dp[i]==pos)
  Insert(i+n,​t,​1);​  Insert(i+n,​t,​1);​
- } + _for(j,1,i){ 
- while(m--){ + if(a[j]<=a[i]&&​dp[j]+1==dp[i]) 
- u=read_int(),​v=read_int();​ + Insert(j+n,i,1);
- Insert(u,​v+n,1); +
- } +
- int flow=solver.Maxflow(s,t); +
- _rep(u,1,n){ +
- for(int i=head[u];~i;i=edge[i].next){ +
- int v=edge[i].to;​ +
- if(v!=s&&edge[i].cap==0){ +
- Next[u]=v-n; +
- Pre[v-n]=u; +
- }+
  }  }
  }  }
- _rep(i,1,n){ + int ans=solver.Maxflow(s,t); 
- if(!Pre[i]){ + enter(ans);​ 
- int pos=i; + Insert(s,1,Inf);​Insert(1,​1+n,Inf); 
- while(pos){ + if(dp[n]==pos){ 
- space(pos); + Insert(n,2*n,Inf); 
- pos=Next[pos];​ + Insert(2*n,t,Inf);
- } +
- puts(""​); +
- }+
  }  }
- enter(n-flow);+ ans+=solver.Maxflow(s,​t);​ 
 + enter(ans);
  return 0;  return 0;
 } }
行 891: 行 1105:
 </​hidden>​ </​hidden>​
  
-====  ​最长不下降子序列问题 ====+====  ​星际转移问题 ====
  
-[[https://​www.luogu.com.cn/​problem/​P2766|洛谷p2766]]+[[https://​www.luogu.com.cn/​problem/​P2754|洛谷p2754]]
  
 === 题意 === === 题意 ===
  
-给定一个正整数序列 ​$x_1,​x_2,​\cdots x_n$。+一共 $n$ 个点，$m$ 条船。每条船有一定容量，并且存在周期性环形航线。
  
-  - 计算其最长不下降子序列的长度 $s$ +设船从航线中的一个点移动到另一个点花费 ​$1$ 个单位的时间，问最少要花多少时间才能把 ​$k$ 个人从起点运到终点。
-  - 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 ​$s$ 的不下降子序列 +
-  - 如果允许在取出的序列中多次使用 $x_1,x_n$，则从给定序列中最多可取出多少个不同的长度为的 ​$s$ 不下降子序列+
  
 === 题解 === === 题解 ===
  
-第一问考虑 ​$\text{dp}$ 求出以第 $i$ 个数结尾的最长序列长度。+考虑按时间拆点，起点连接源点，终点连接汇点。
  
-第二问先考虑只允许使用一次这个限制条件，只需要把每个点拆成入点和出点，然后连一条容量为 $1$ 的边即可。+每个位置的相邻时间点连接一条容量无限大的边，表示停留在该位置一个单位时间。
  
-接下若满足 $j\lt i,a_j\le a_i,​\text{dp}_j+1==\text{dp}_i$，则连一条 $j\to i$ 的容量为 $1$ 的边。+然后枚举时间，根据时间和飞船航线加边，每次在残量网络上跑最大流并累加到总流量，总流量不小于 ​$k$ 时结束枚举。
  
-最后考虑从源点向 $\text{dp}_i==1$ ​的点连一条容量为 $1$ 的边，从 $\text{dp}_i==s$ 的点向汇点连一条容量为 $1$ 的边。 +至于无解的判定，可以一开始用并查集维护一下连通性。
- +
-最后跑最大流即可求出第二问答案。 +
- +
-对第三问，考虑把第 $1,n$ 个点的入点和出点的连边容量改为 ​ $\inf$，同时把从源点到第 $1$ 个的连边的容量改为 $\inf$。 +
- +
-如果 $\text{dp}_n==s$，还需要把从第 $n$ 个点向汇点的连边的容量改为 $\inf$，然后重新跑一遍最大流。 +
- +
-但实际编程中不需要修改边，额外添加边即可。同时也不需要重新跑最大流，在残量网络上跑最大流然后累加上第二问答案即可。 +
- +
-需要注意 $s=1$ 的特例，题目需要求不同的不下降子序列就是为了防止此时答案为 $\inf$ 的情况。+
  
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
-#include <​iostream>​ +const int MAXN=1e5+5,MAXM=2e5+5,​Inf=0x7fffffff;​
-#include <​cstdio>​ +
-#include <​cstdlib>​ +
-#include <​algorithm>​ +
-#include <​string>​ +
-#include <​sstream>​ +
-#include <​cstring>​ +
-#include <​cctype>​ +
-#include <​cmath>​ +
-#include <​vector>​ +
-#include <​set>​ +
-#include <​map>​ +
-#include <​stack>​ +
-#include <​queue>​ +
-#include <​ctime>​ +
-#include <​cassert>​ +
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) +
-#define _rep(i,a,b) for(int i=(a);​i<​=(b);​++i) +
-#define mem(a,b) memset(a,​b,​sizeof(a)) +
-using namespace std; +
-typedef long long LL; +
-inline int read_int(){ +
- int t=0;bool sign=false;​char c=getchar();​ +
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
- return sign?​-t:​t;​ +
-} +
-inline LL read_LL(){ +
- LL t=0;bool sign=false;​char c=getchar();​ +
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
- return sign?​-t:​t;​ +
-} +
-inline char get_char(){ +
- char c=getchar();​ +
- while(c=='​ '​||c=='​\n'​||c=='​\r'​)c=getchar();​ +
- return c; +
-} +
-inline void write(LL x){ +
- register char c[21],​len=0;​ +
- if(!x)return putchar('​0'​),​void();​ +
- if(x<​0)x=-x,​putchar('​-'​);​ +
- while(x)c[++len]=x%10,​x/​=10;​ +
- while(len)putchar(c[len--]+48);​ +
-} +
-inline void space(LL x){write(x),​putchar('​ ');} +
-inline void enter(LL x){write(x),​putchar('​\n'​);​} +
-const int MAXN=1005,MAXM=5e5+5,​Inf=0x7fffffff;​+
 struct Edge{ struct Edge{
  int to,​cap,​next;​  int to,​cap,​next;​
行 1036: 行 1191:
  }  }
 }solver; }solver;
-int a[MAXN],dp[MAXN],f[MAXN],pos;+const int MAXS=25; 
 +vector<​int>​ g[MAXS]; 
 +int p[MAXS],f[MAXS],T[MAXS]; 
 +int Find(int x){return x==p[x]?​x:​p[x]=Find(p[x]);}
 int main() int main()
 { {
- int n=read_int();​+ Clear(); 
 + int n=read_int()+2,​m=read_int(),​k=read_int(),​s=MAXN-2,​t=MAXN-1,​x,​y;
  _rep(i,​1,​n)  _rep(i,​1,​n)
- a[i]=read_int(); + p[i]=i; 
- f[pos=0]=-Inf; + _for(i,0,m){ 
- _rep(i,1,n){ + f[i]=read_int(),​T[i]=read_int(); 
- if(a[i]>=f[pos]){ + _for(j,0,T[i]){ 
- f[++pos]=a[i]; + x=read_int();​ 
- dp[i]=pos;+ if(x==0) 
 + x=n-1; 
 + else if(x==-1) 
 + x=n; 
 + g[i].push_back(x);
  }  }
- else{ + _for(j,1,T[i]){ 
- int t=upper_bound(f,f+pos+1,a[i])-f; + x=Find(g[i][j-1]),y=Find(g[i][j]); 
- f[t]=a[i]; + if(x!=y) 
- dp[i]=t;+ p[x]=y;
  }  }
  }  }
- enter(pos);​ + if(Find(n-1)!=Find(n)){ 
- if(pos==1){ + puts("​0"​);
- sort(a+1,a+n+1); +
- int ans=unique(a+1,a+n+1)-a-1; +
- enter(ans); +
- enter(ans);+
  return 0;  return 0;
  }  }
- int s=2*n+1,t=2*n+2;+ Insert(s,​n-1,​Inf);​Insert(n,​t,​Inf);​ 
 + int ans=0; 
 + for(int flow=0;​flow<​k;​ans++){ 
 + _for(i,​1,​n) 
 + Insert(i+ans*n,​i+(ans+1)*n,​Inf);​ 
 + Insert((ans+2)*n,(ans+1)*n,Inf); 
 + _for(i,​0,​m) 
 + Insert(g[i][ans%T[i]]+ans*n,​g[i][(ans+1)%T[i]]+(ans+1)*n,​f[i]);​ 
 + flow+=solver.Maxflow(s,t); 
 + } 
 + enter(ans);​ 
 + return 0; 
 +} 
 +</​code>​ 
 +</​hidden>​ 
 + 
 +====  餐巾计划问题 ==== 
 + 
 +[[https://​www.luogu.com.cn/​problem/​P1251|洛谷p1251]] 
 + 
 +=== 题意 === 
 + 
 +一个餐厅第 $i$ 天需要 $r_i$ 条新餐巾，每条新餐巾用完后得到旧餐巾，一开始餐厅没有餐巾。 
 + 
 +买一条新餐巾费用为 $p$；快洗一条旧餐巾时间为 $m$ 天，费用为 $f$；慢洗一条旧餐巾时间为 $n$ 天，费用为 $s$。 
 + 
 +数据保证 $f\gt s,m\lt n$，问餐厅营业 $N$ 天的最小花费。  
 + 
 +=== 题解 === 
 + 
 +把一天分成一天的开始和一天的结束，一天的开始需要提供 $r_i$ 条新餐巾，于是连一条容量为 $r_i$ 费用为 $0$ 的边到汇点。 
 + 
 +接下来考虑三种获取新餐巾的操作。首先可以买新餐巾，对应源点连一条容量为 $\inf$ 费用为 $p$ 的边到当天的开始。 
 + 
 +另外也可以通过清洗之前的旧餐巾获得。不妨假设如果旧餐巾洗完就会被立即使用，不然可以留到以后再洗。这样假设的目的是减少连边数量。 
 + 
 +于是第 $i$ 天的结束向第 $i+m$ 天的开始连一条容量为 $\inf$ 费用为 $f$ 的边，向第 $i+n$ 天的开始连一条容量为 $\inf$ 费用为 $s$ 的边。 
 + 
 +再考虑维护旧餐巾，旧餐巾可以通过两种方式获取。 
 + 
 +首先一天的结束将有 $r_i$ 条新餐巾变成旧餐巾，于是从源点连一条容量为 $r_i$ 费用为 $0$ 的边到一天的结束。 
 + 
 +另外旧餐巾也可以继承前一天剩下的未被清洗的旧餐巾，对应每天结束向第二天结束连一条容量为 $\inf$ 费用为 $0$ 的边。 
 + 
 +最后跑最小费用最大流即可。 
 + 
 +<hidden 查看代码>​ 
 +<code cpp> 
 +const int MAXN=5000,​MAXM=15000,​Inf=0x7fffffff; 
 +struct Edge{ 
 + int to,​cap,​w,​next;​ 
 + Edge(int to=0,int cap=0,int w=0,int next=0){ 
 + this->​to=to;​ 
 + this->​cap=cap;​ 
 + this->​w=w;​ 
 + this->​next=next;​ 
 + } 
 +}edge[MAXM<<​1];​ 
 +int head[MAXN],​edge_cnt;​ 
 +void Clear(){mem(head,​-1);​edge_cnt=0;​}//​边从0开始编号  
 +void Insert(int u,int v,int w,int c){ 
 + edge[edge_cnt]=Edge(v,​c,​w,​head[u]);​ 
 + head[u]=edge_cnt++;​ 
 + edge[edge_cnt]=Edge(u,​0,​-w,​head[v]);​ 
 + head[v]=edge_cnt++;​ 
 +} 
 +struct Dinic{ 
 + int s,t; 
 + int pos[MAXN],​dis[MAXN];​ 
 + bool inque[MAXN];​ 
 + bool spfa(){ 
 + mem(dis,​127/​3);​ 
 + queue<​int>​q;​ 
 + q.push(s);​ 
 + inque[s]=true,​dis[s]=0,​pos[s]=head[s];​ 
 + while(!q.empty()){ 
 + int u=q.front();​q.pop();​ 
 + inque[u]=false;​ 
 + for(int i=head[u];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(dis[u]+edge[i].w<​dis[v]&&​edge[i].cap){ 
 + dis[v]=dis[u]+edge[i].w,​pos[v]=head[v];​ 
 + if(!inque[v]){ 
 + q.push(v);​ 
 + inque[v]=true;​ 
 + } 
 + } 
 + } 
 + } 
 + return dis[t]!=dis[0];​ 
 + } 
 + int dfs(int u,int max_flow){ 
 + if(u==t||!max_flow) 
 + return max_flow; 
 + int flow=0,​temp_flow;​ 
 + inque[u]=true;​ 
 + for(int &​i=pos[u];​~i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(!inque[v]&&​dis[u]+edge[i].w==dis[v]&&​(temp_flow=dfs(v,​min(max_flow,​edge[i].cap)))){ 
 + edge[i].cap-=temp_flow;​ 
 + edge[i^1].cap+=temp_flow;​ 
 + flow+=temp_flow;​ 
 + max_flow-=temp_flow;​ 
 + if(!max_flow) 
 + break;​ 
 + } 
 + } 
 + inque[u]=false;​ 
 + return flow; 
 + } 
 + void MCMF(int s,int t,int &​flow,​LL &​cost){ 
 + this->​s=s;​this->​t=t;​ 
 + cost=flow=0;​ 
 + int temp_flow;​ 
 + mem(inque,​0);​ 
 + while(spfa()){ 
 + temp_flow=dfs(s,​Inf);​ 
 + flow+=temp_flow;​ 
 + cost+=1LL*temp_flow*dis[t];​ 
 + } 
 + } 
 +}solver; 
 +int a[MAXN]; 
 +int main() 
 +{
  Clear();  Clear();
 + int n=read_int(),​s=n<<​1|1,​t=s+1;​
 + _rep(i,​1,​n)
 + a[i]=read_int();​
 + int c1=read_int(),​t2=read_int(),​c2=read_int(),​t3=read_int(),​c3=read_int();​
  _rep(i,​1,​n){  _rep(i,​1,​n){
- Insert(i,i+n,1); + Insert(s,i+n,0,a[i]); 
- if(dp[i]==1) + Insert(i,t,0,a[i]); 
- Insert(s,​i,​1); + Insert(s,​i,​c1,Inf); 
- if(dp[i]==pos) + if(i+t2<=n){ 
- Insert(i+n,t,1); + Insert(i+n,i+t2,c2,Inf); 
- _for(j,​1,​i){ + if(i+t3<=n) 
- if(a[j]<=a[i]&&​dp[j]+1==dp[i]) + Insert(i+n,i+t3,c3,Inf);
- Insert(j+n,i,1);+
  }  }
  }  }
- int ans=solver.Maxflow(s,t); + _for(i,1,n) 
- enter(ans);​ + Insert(i+n,i+n+1,0,Inf); 
- Insert(s,1,Inf);​Insert(1,​1+n,Inf); + int flow;LL cost; 
- if(dp[n]==pos){ + solver.MCMF(s,t,flow,cost); 
- Insert(n,2*n,Inf); + enter(cost);
- Insert(2*n,​t,​Inf); +
- } +
- ans+=solver.Maxflow(s,t); +
- enter(ans);+
  return 0;  return 0;
 } }
 </​code>​ </​code>​
 </​hidden>​ </​hidden>​
 +
 +
 +
2020-2021/teams/legal_string/jxm2001/图论_3.1595320098.txt.gz · 最后更改: 2020/07/21 16:28 由 jxm2001

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3