【置顶】关于这个博客的一切

记录时光与梦想

「网络流 24 题」最长递增子序列-dp+网络最大流

给定正整数序列 $x_1 \sim x_n$ ,以下递增子序列均为非严格递增。

  1. 计算其最长递增子序列的长度 $s$ 。

  2. 计算从给定的序列中最多可取出多少个长度为 $s$ 的递增子序列。

  3. 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$ ,则从给定序列中最多可取出多少个长度为 $s$ 的递增子序列。

链接

LOJ6005

题解

这个问题需要用dp和网络流搭配解决。

第一问:直接 $O(n^2)$ dp 即可。


第二问:在第一问的基础上,我们考虑网络流。

我们把每个点拆成两个点: $(i,0)$ 和 $(i,1)$

  • $S$ 向所有 $dp[i] = 1$ 的 $(i,0)$ 连边
  • 所有 $dp[i] = s$ 的点向 T 连边
  • 对于每个 $j$,向所有满足: $j < i \le n,x[j] \le x[i],dp[j] + 1 = dp[i]$ ,连一条 $(i,1)$ 向 $(j,0)$ 的边
  • 最后每个 $(i,0)$ 向 $(i,1)$ 连边。

然后 dinic 大概就可以了。


第三问:把四个边增加到正无穷:$(1,0) \rightarrow (1,1)$ , $(n,0) \rightarrow (n,1)$ , $S \rightarrow (1,0)$ , $(n,1) \rightarrow T$(如果有) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

const int MAXN = 1100,MAXM = MAXN*MAXN;

struct Edge{
int from,to;
int cap,flow;
int nex;
}edge[MAXM];
int fir[MAXN],ecnt = 2;
void addedge(int a,int b,int c){
edge[ecnt] = (Edge){a,b,c,0,fir[a]};fir[a] = ecnt++;
edge[ecnt] = (Edge){b,a,0,0,fir[b]};fir[b] = ecnt++;
}

int dis[MAXN];
bool bfs(int s,int t){
static queue<int> q;
memset(dis,0,sizeof(dis));while(!q.empty()) q.pop();
dis[s] = 1,q.push(s);
while(!q.empty()){
int x = q.front();q.pop();
for(int e = fir[x];e;e = edge[e].nex){
int v = edge[e].to;
if(!dis[v] && edge[e].cap > edge[e].flow){
dis[v] = dis[x]+1;q.push(v);
}
}
}
return dis[t];
}
int dfs(int x,int t,int limit =inf){
if(limit == 0 || x == t) return limit;
int sumf = 0;
for(int e = fir[x];e;e = edge[e].nex){
int v = edge[e].to;
if(dis[v] == dis[x]+1){
int f = dfs(v,t,min(limit,edge[e].cap - edge[e].flow));
if(f){
sumf += f,limit -= f;
edge[e].flow += f,edge[e^1].flow -= f;
if(limit == 0) break;
}
}
}
return sumf;
}

int dinic(int s,int t){
static int ans = 0;
while(bfs(s,t)) ans += dfs(s,t);
return ans;
}

int n;
int x[MAXN],dp[MAXN];

void init(){
scanf("%d",&n);
for(int i = 1;i<=n;i++) scanf("%d",&x[i]);
}

void solve(){
int ans = 0,S = n+1,T = 2*n+3;// 0 -> n && n+1 -> 2*n+1
for(int i = 1;i<=n;i++) addedge(i,i+n+1,1);
for(int i = 1;i<=n;i++){
for(int j = 0;j<i;j++)if(x[j] <= x[i]) dp[i] = max(dp[i],dp[j]+1);
for(int j = 0;j<i;j++)if(x[j] <= x[i] && dp[j] + 1 == dp[i]) addedge(j+n+1,i,1);
ans = max(ans,dp[i]);
}
for(int i = 1;i<=n;i++) if(dp[i] == ans) addedge(i+n+1,T,1);
printf("%d\n",ans);
printf("%d\n",dinic(S,T));
addedge(1,1+n+1,n*n-1),addedge(n,n+n+1,n*n-1);
addedge(S,1,n*n-1);
if(dp[n] == ans) addedge(n+n+1,T,n*n-1);
printf("%d\n",dinic(S,T));
}

int main(){
init(),solve();
return 0;
}

「网络流 24 题」圆桌聚餐-网络最大流

假设有来自 $m$ 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 $r_i$ 。会议餐厅共有 $n$ 张餐桌,每张餐桌可容纳 $c_i$ 个代表就餐。

为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。

试设计一个算法,给出满足要求的代表就餐方案。

「网络流 24 题」魔术球-二分图最大匹配

假设有 $n$ 根柱子,现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1, 2, 3, 4, \cdots$ 的球。

  1. 每次只能在某根柱子的最上面放球。
  2. 在同一根柱子中,任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 $n$ 根柱子上最多能放多少个球。

「网络流 24 题」最小路径覆盖-二分图最大匹配

给定有向图 $G = (V, E)$。设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合。如果 $V$ 中每个顶点恰好在 $P$ 的一条路上,则称 $P$ 是 $G$ 的一个路径覆盖。 $P$ 中路径可以从 $V$ 的任何一个顶点开始,长度也是任意的,特别地,可以为 $0$ 。 $G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图 $G$ 的最小路径覆盖。

「网络流 24 题」太空飞行计划-最大权闭合子图

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $E = \{ E_1, E_2, \cdots, E_m \}$ ,和进行这些实验需要使用的全部仪器的集合 $I = \{ I_1, I_2, \cdots, I_n \}$ 。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j \subseteq I$ 。配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。W 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。

「网络流 24 题」搭配飞行员-二分图最大匹配

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

「SPOJ26374」QTREE5-LCT

你被给定一棵 $n$ 个点的树,点从 $1$ 到 $n$ 编号。每个点可能有两种颜色:黑或白。我们定义 $dist(a,b)$ 为点 $a$ 至点 $b$ 路径上的边个数。一开始所有的点都是黑色的。

要求作以下操作:

  • 0 i 将点 $i$ 的颜色反转(黑变白,白变黑)
  • 1 v 询问 $dist(u,v)$ 的最小值。$u$ 点必须为白色( $u$ 与 $v$ 可以相同),显然如果 $v$ 是白点,查询得到的值一定是 $0$ 。

特别地,如果作 1 操作时树上没有白点,输出 $-1$ 。

「SPOJ16580」QTREE7-LCT

一棵树,每个点初始有个点权和颜色(输入会给你)

  • 0 u : 询问所有 $u,v$ 路径上的最大点权,要满足 $u,v$ 路径上所有点的颜色都相同
  • 1 u : 反转 $u$ 的颜色
  • 2 u w :把 $u$ 的点权改成 $w$

「SPOJ16549」QTREE6-LCT

给你一棵 $n$ 个点的树,编号 $1$~$n$ 。每个点可以是黑色,可以是白色。初始时所有点都是黑色。有两种操作:

  • 0 u :询问有多少个节点 $v$ 满足路径 $u$ 到 $v$ 上所有节点(包括端点)都拥有相同的颜色
  • 1 u :翻转 $u$ 的颜色
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×