2020-2021:teams:legal_string:组队训练比赛记录:缓冲区
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/08/18 20:47] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/10/04 17:00] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ===== C. Dance Party ===== | + | ===== H. travel ===== |
| ==== 题意 ==== | ==== 题意 ==== | ||
| - | 给定 $n\times 2$ 的二分图。对左部每个点，仅和右部 $k_i$ 个点不连边。求二分图最大匹配。 | + | 给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。 |
| ==== 题解 ==== | ==== 题解 ==== | ||
| - | 设 $k=\max_{i=1}^n k_i$。 | + | 设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。 |
| - | 先进行预匹配，每个左部点任选一个还未被匹配且有连边的右部点匹配，可以用 $\text{set}$ 维护所有未匹配的右部点，时间复杂度 $O(nk\log n)$。 | + | 我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。 |
| - | 接下来剩下的未匹配的点一定不超过 $k$ 个，对每个点考虑匈牙利算法匹配， 总时间复杂度为 $O(km)$。 | + | 如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。 |
| - | $O(m)\sim O(n^2)$，考虑优化。假定现在需要对点 $i$ 进行匈牙利算法，将右部与点 $i$ 不相邻的点染黑，其余右部点染白。 | + | 考虑状态转移，利用生成链的合并，不难有 |
| - | 对除点 $i$ 以外的左部点，仅保留与黑点相关的连边，这样 $O(m)\sim O(nk)$，总时间复杂度 $O\left(nk^2\right)$ 足以通过此题。 | + | $$ |
| + | \text{dp}(u,0,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,0,j)\\ | ||
| + | \text{dp}(u,1,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,1,j)+a_u\\ | ||
| + | \text{dp}(u,1,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,0,j)\\ | ||
| + | \text{dp}(u,2,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,1,j)\\ | ||
| + | \text{dp}(u,2,i+j)\gets \text{dp}(u,2,i)+\text{dp}(v,0,j) | ||
| + | $$ | ||
| - | 关于算法的正确性，假设在原图上存在一条从 $i$ 出发的增广路，且增广路上除了 $i$ 以外有其他点的失配边指向白点。 | + | 注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。 |
| - | 找到增广路上的最后一个白点，直接将 $i$ 的失配边指向该点然后保留原增广路的剩余部分也可以一条增广路。 | + | 初始状态为 $\text{dp}(u,1,0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有 |
| - | 同时该增广路上除了 $i$ 其他点的失配边都指向黑点。因此只要原图存在一条从 $i$ 出发的增广路则只保留与黑点相关的连边也可以得到一条增广路。 | + | $$ |
| + | \text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1)) | ||
| + | $$ | ||
| + | |||
| + | 最终答案为 $\text{dp}(1,0,3)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。 | ||
| + | |||
| + | [[http://tokitsukaze.live/2018/07/24/2018niuke2.H/|参考资料]] | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | const int MAXN=3e4+5,MAXK=105; | + | const int MAXN=4e5+5,MAXK=4; |
| struct Edge{ | struct Edge{ | ||
| int to,next; | int to,next; | ||
| - | }edge[MAXN*MAXK]; | + | }edge[MAXN<<1]; |
| - | int head[MAXN],edge_cnt; | + | int a[MAXN],head[MAXN],edge_cnt; |
| + | LL dp[MAXN][3][MAXK],tmp[3][MAXK]; | ||
| void Insert(int u,int v){ | void Insert(int u,int v){ | ||
| edge[++edge_cnt]=Edge{v,head[u]}; | edge[++edge_cnt]=Edge{v,head[u]}; | ||
| head[u]=edge_cnt; | head[u]=edge_cnt; | ||
| } | } | ||
| - | bitset<MAXN> bt[MAXN]; | + | void Max(LL &a,LL b){ |
| - | vector<int> g[MAXN]; | + | if(b>a) |
| - | namespace KM{ | + | a=b; |
| - | set<int> s; | + | } |
| - | int match[MAXN],vis[MAXN]; | + | void dfs(int u,int fa){ |
| - | bool dfs(int u,int k){ | + | dp[u][1][0]=a[u]; |
| - | if(vis[u]==k) | + | for(int i=head[u];i;i=edge[i].next){ |
| - | return false; | + | int v=edge[i].to; |
| - | vis[u]=k; | + | if(v==fa)continue; |
| - | for(int i=head[u];i;i=edge[i].next){ | + | dfs(v,u); |
| - | int v=edge[i].to; | + | _for(i,0,3)_for(j,0,MAXK) |
| - | if(!match[v]||dfs(match[v],k)) | + | tmp[i][j]=dp[u][i][j]; |
| - | return match[v]=u,true; | + | _for(i,0,MAXK)_for(j,0,MAXK-i){ |
| + | Max(tmp[0][i+j],dp[u][0][i]+dp[v][0][j]); | ||
| + | Max(tmp[1][i+j],dp[u][0][i]+dp[v][1][j]+a[u]); | ||
| + | Max(tmp[1][i+j],dp[u][1][i]+dp[v][0][j]); | ||
| + | Max(tmp[2][i+j],dp[u][1][i]+dp[v][1][j]); | ||
| + | Max(tmp[2][i+j],dp[u][2][i]+dp[v][0][j]); | ||
| } | } | ||
| - | return false; | + | _for(i,0,3)_for(j,0,MAXK) |
| - | } | + | dp[u][i][j]=tmp[i][j]; |
| - | bool get_pair(int n){ | + | |
| - | _rep(u,1,n) | + | |
| - | s.insert(u); | + | |
| - | vector<int> vec; | + | |
| - | _rep(u,1,n){ | + | |
| - | bool flag=true; | + | |
| - | for(int v:s){ | + | |
| - | if(!bt[u][v]){ | + | |
| - | match[v]=u; | + | |
| - | s.erase(v); | + | |
| - | flag=false; | + | |
| - | break; | + | |
| - | } | + | |
| - | } | + | |
| - | if(flag) | + | |
| - | vec.push_back(u); | + | |
| - | } | + | |
| - | for(int i:vec){ | + | |
| - | mem(head,0); | + | |
| - | edge_cnt=0; | + | |
| - | _rep(u,1,n){ | + | |
| - | for(int v:g[i]){ | + | |
| - | if(!bt[u][v]) | + | |
| - | Insert(u,v); | + | |
| - | } | + | |
| - | } | + | |
| - | _rep(v,1,n){ | + | |
| - | if(!bt[i][v]) | + | |
| - | Insert(i,v); | + | |
| - | } | + | |
| - | if(!dfs(i,i)) | + | |
| - | return false; | + | |
| - | } | + | |
| - | return true; | + | |
| } | } | ||
| + | _for(i,1,MAXK) | ||
| + | Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1])); | ||
| } | } | ||
| - | int ans[MAXN]; | ||
| int main() | int main() | ||
| { | { | ||
| int n=read_int(); | int n=read_int(); | ||
| - | _rep(u,1,n){ | + | _rep(i,1,n) |
| - | int k=read_int(); | + | a[i]=read_int(); |
| - | while(k--){ | + | _for(i,1,n){ |
| - | int v=read_int(); | + | int u=read_int(),v=read_int(); |
| - | g[u].push_back(v); | + | Insert(u,v); |
| - | bt[u][v]=1; | + | Insert(v,u); |
| - | } | + | |
| - | } | + | |
| - | if(KM::get_pair(n)){ | + | |
| - | _rep(i,1,n) | + | |
| - | ans[KM::match[i]]=i; | + | |
| - | _rep(i,1,n) | + | |
| - | space(ans[i]); | + | |
| } | } | ||
| - | else | + | dfs(1,0); |
| - | puts("-1"); | + | enter(dp[1][0][3]); |
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/组队训练比赛记录/缓冲区.1629290869.txt.gz · 最后更改: 2021/08/18 20:47 由 jxm2001
