铁人两项题解

题解"/>

铁人两项题解

铁人两项：

洛谷P4630 [APIO2018] Duathlon 铁人两项

题目描述
比特镇的路网由 m 条双向道路连接的 n 个交叉路口组成。
最近，比特镇获得了一场铁人两项锦标赛的主办权。这场比赛共有两段赛程：选手先完成一段长跑赛程，然后骑自行车完成第二段赛程。
比赛的路线要按照如下方法规划：
先选择三个两两互不相同的路口s,c和f，分别作为比赛的起点、切换点（运动员在长跑到达这个点后，骑自行车前往终点）、终点。
选择一条从s出发，经过c最终到达f的路径。考虑到安全因素，选择的路径经过同一个点至多一次。
在规划路径之前，镇长想请你帮忙计算，总共有多少种不同的选取s,c和f的方案，使得在第2步中至少能设计出一条满足要求的路径。

输入输出格式
输入格式：
第一行包含两个整数 n和 m ，分别表示交叉路口和双向道路的数量。
接下来 m行，每行两个整数ui和vi，示存在一条双向道路连接交叉路口(1<=ui,vi<=n;ui!=vi)。
保证任意两个交叉路口之间，至多被一条双向道路直接连接。

输出格式：
输出一行，包括一个整数，表示能满足要求的不同的选取s,c和f的方案数。

输入输出样例
输入样例#1：
4 3
1 2
2 3
3 4
输出样例#1：
8
输入样例#2：
4 4
1 2
2 3
3 4
4 2
输出样例#2：
14
说明
提示

在第一个样例中，有以下 8种不同的选择(s,c,f)的方案： (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (3, 2, 1), (4, 2, 1), (4, 3, 1), (4, 3, 2)。

在第二个样例中，有以下 14种不同的选择(s,c,f) 的方案：(1,2,3),(1,2,4),(1,3,4),(1,4,3),(2,3,4),(2,4,3),(3,2,1),(3,2,4),(3,4,1),(3,4,2),(4,2,1),(4,2,3),(4,3,1),(4,3,2)。

子任务（注：这里给出的子任务与本题在这里的最终评测无关，仅供参考）

Subtask 1(points: 55): n≤10,m≤100
Subtask 2(points: 1111): n≤50,m≤100
Subtask 3(points: 88): n≤100000，每个交叉路口至多作为两条双向道路的端点
Subtask 4(points: 1010): n≤1000，在路网中不存在环
Subtask 5(points: 13): n≤100000，在路网中不存在环
Subtask 6(points: 15): n≤1000，对于每个交叉路口，至多被一个环包含
Subtask 7(points: 20): n≤100000，对于每个交叉路口，至多被一个环包含
Subtask 8(points: 8): n≤1000,m≤2000
Subtask 9(points: 10): n≤100000,m≤200000

题意：
求两点u到v的中转站(u到v路径上不为u、v的点)的方案数(点数)
答案为任意u、v的方案数和。
思路：
圆方树+树型DP。
先考虑两点u到v的方案数。
我们考虑如何赋值。
对于每条路径，定从一原点开始，一原点结束。
图中所经过的点双，我们显然都可以选作中转站。
但问题是割点同时属于多个点双(在一条链上只可能属于两个)。
若经过n个方点(点双)，只会经过n-1个割点；
加上首尾两端不算的点，也被路上的点双算入；
也就是说走一个路上的圆点就减1；
不妨将圆点权值赋值为-1，方点权值赋值为点双含点数量；
则u到v方案数为u到v权值和，可以用lca和前缀和求解。
但要求任意u到v的方案，且已将方案问题转化为权值问题；
考虑树型DP。
对于每个点我们可以统计它被多少条路径经过，
它的贡献即为w*经过的路径数。
显然，经过这个点的路径有两种情况：
<1>.从这棵子树到另一棵子树。
<2>.从这个点到子树(这个点为圆点)。
只需按如下代码做即可：

 1 void dfs(int u,int fa)
 2 {
 3     siz[u]=(u<=t1);
 4     for(int i=head2[u];i;i=g[i].nxt)
 5         if(g[i].to!=fa)
 6         {
 7             dfs(g[i].to,u),ans+=2ll*w[u]*siz[u]*siz[g[i].to];
 8             siz[u]+=siz[g[i].to];
 9         }
10     ans+=2ll*w[u]*siz[u]*(num-siz[u]);
11     //u到v和v到u算两条路径 
12 }

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=200006,M=400006;
 4 int head[N],head2[N],low[N],dfn[N],siz[N],w[N],n,m;
 5 int deep=0,cnt=0,top=0,s[N],t1,t2,num=0;
 6 long long ans=0;
 7 struct edge
 8 {
 9     int nxt,to;
10 }e[M<<1],g[M<<1];
11 inline int read()
12 {
13     int T=0,F=1; char ch=getchar();
14     while(ch<'0'||ch>'9'){if(ch=='-') F=-1; ch=getchar();}
15     while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
16     return F*T;
17 }
18 inline void add(int u,int v){e[++cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt;}
19 inline void add2(int u,int v){g[++cnt].nxt=head2[u]; g[cnt].to=v; head2[u]=cnt;}
20 void tarjan(int u)
21 {
22     dfn[u]=low[u]=++deep; s[++top]=u; ++num;
23     int t;
24     for(int i=head[u];i,t=e[i].to;i=e[i].nxt)
25     {
26         if(!dfn[t])
27         {
28             tarjan(t),low[u]=min(low[u],low[t]);
29             if(low[t]>=dfn[u])
30             {
31                 ++n; add2(n,u),add2(u,n); ++w[n];
32                 while(s[top+1]!=t) add2(s[top],n),add2(n,s[top]),++w[n],--top;
33             }
34         }
35         else low[u]=min(low[u],dfn[t]);
36     }
37 }
38 void dfs(int u,int fa)
39 {
40     siz[u]=(u<=t1);
41     for(int i=head2[u];i;i=g[i].nxt)
42         if(g[i].to!=fa)
43         {
44             dfs(g[i].to,u),ans+=2ll*w[u]*siz[u]*siz[g[i].to];
45             siz[u]+=siz[g[i].to];
46         }
47     ans+=2ll*w[u]*siz[u]*(num-siz[u]);
48     //u到v和v到u算两条路径 
49 }
50 int main()
51 {
52     n=read(),m=read();
53     for(register int i=1;i<=m;++i) t1=read(),t2=read(),add(t1,t2),add(t2,t1);
54     cnt=0; t1=n;
55     for(register int i=1;i<=n;++i) w[i]=-1;
56     for(register int i=1;i<=t1;++i) if(!dfn[i]) top=0,num=0,tarjan(i),dfs(i,0);
57     printf("%lld\n",ans);
58     return 0;
59 } 

转载于:.html