【APIO2018】铁人两项(圆方树,动态规划)
规划 动态
2023-09-11 14:14:40 时间
【APIO2018】铁人两项(圆方树,动态规划)
题面
题解
嘤嘤嘤,APIO的时候把一个组合数写成阶乘了,然后这题的70多分没拿到
首先一棵树是很容易做的,随意指定起点终点就只能在两点路径上选择第三点。那么考虑过中点的路径个数,就可以很方便的\(dp\)计算了。
对于仙人掌而言,把环全部缩成点,转成树,缩起来的点额外定义一个点权,同样可以直接在树上做\(dp\),额外考虑环自身内部的贡献。
那么对于一般图而言,构建圆方树,那么选定起点和终点后,还是只能选择两点路径之间的圆点。定义方点的权值为点双的点数和,显然选定起点终点后,两点间的贡献就是路径上的点权和。然而这样子圆点会被算多,所以圆点的点权为\(-1\)。
那么又是一棵树了,直接枚举中间点考虑过中间点的路径个数即可。
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define MAX 100100
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Graph
{
struct Line{int v,next;}e[MAX<<3];
int h[MAX<<1],cnt=1;
inline void Add(int u,int v)
{
e[cnt]=(Line){v,h[u]};h[u]=cnt++;
e[cnt]=(Line){u,h[v]};h[v]=cnt++;
}
}Gr,Tr;
int n,m;ll ans;
int dfn[MAX],low[MAX],tim,S[MAX],top,tot,V[MAX<<1];
int size[MAX<<1],Size;
void Tarjan(int u)
{
dfn[u]=low[u]=++tim;S[++top]=u;++Size;
for(int i=Gr.h[u];i;i=Gr.e[i].next)
{
int v=Gr.e[i].v;
if(!dfn[v])
{
Tarjan(v);low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
Tr.Add(++tot,u);int x;V[tot]=1;
do{x=S[top--];Tr.Add(tot,x);++V[tot];}while(x!=v);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void dp(int u,int ff)
{
size[u]=u<=n;
for(int i=Tr.h[u];i;i=Tr.e[i].next)
{
int v=Tr.e[i].v;if(v==ff)continue;
dp(Tr.e[i].v,u);
ans+=2ll*V[u]*size[u]*size[v];
size[u]+=size[v];
}
ans+=2ll*V[u]*size[u]*(Size-size[u]);
}
int main()
{
n=tot=read();m=read();
for(int i=1;i<=m;++i)Gr.Add(read(),read());
for(int i=1;i<=n;++i)V[i]=-1;
for(int i=1;i<=n;++i)if(!dfn[i])Size=0,Tarjan(i),dp(i,0);
printf("%lld\n",ans);
return 0;
}
相关文章
- Java实现 LeetCode 740 删除与获得点数(递推 || 动态规划?打家劫舍Ⅳ)
- Java实现 LeetCode 629 K个逆序对数组(动态规划+数学)
- 动态规划题目汇总
- 数据结构和算法—动态规划
- 数据结构和算法—动态规划
- (动态规划)母牛生小牛问题
- LeetCode-788. 旋转数字【暴力,动态规划,字符串,数学】
- LeetCode-808. 分汤【动态规划,概论与统计,记忆化搜索】
- Leetcode学习计划之动态规划入门day14(1314,120)
- Leetcode学习计划之动态规划入门day10(413,91)
- Leetcode学习计划之动态规划入门day4(55,45)
- Algorithm:C++语言实现之动态规划算法相关(矩阵连乘状态转移方程、字符串的交替连接、分析格网棋盘的特点、最短路线问题、生产计划问题、动态规划解下列非线性规划)
- 【无人机】基于灰狼优化算法的无人机路径规划问题研究(Matlab代码实现)
- 【LeetCode Python实现】300. 最长递增子序列(中等)动态规划
- 91. 解码方法-深度优先遍历法和动态规划算法
- 面试题 17.09. 第 k 个数-动态规划
- 1043. 分隔数组以得到最大和-动态规划算法
- [LeetCode] 303. 区域和检索 - 数组不可变 ☆(动态规划)
- python 动态规划求解单源最短路径
- hdu2571 命运 动态规划Dp
- 建模算法(十一)——目标规划
- leetcode算法之动态规划总结(11种DP类型,70道全部搞懂)——总结非常全面
- 动态规划_C#
- 机器人控制算法八之路径规划算法:RRT、RRT-Connect、Dynamic-Domain RRTs*
- Kubernetes 企业集群建设规划
- 一文解析动态规划中的背包问题