【题解】APIO2018 Duathlon 铁人两项
标签：nbsp bit include col signed turn 匹配 中间 tchar
这题真的好水啊……首先对于给出的图建立圆方树，然后我们分类讨论每一个点作为中间的中转站出现的情况有多少种，累积到 \(ans\) 中。
对于圆点：在任意两个子树内分别选出一个节点都是合法的。
对于方点：连接向方点的点均为处于一个双联通分量中的点，彼此之间两两可。所以若我们让这个双联通分量上的一个点作为中转站，在其他任意的两棵子树内挑出两个点来都是合法的。这样乍一看好像是 \(n^{2}\) 的统计方法，我们不妨改变一下：因为答案是累加起来的，我们分别考虑每一棵子树对于答案造成的贡献。这一棵子树中的点可以和另一棵子树内的点任意匹配选出两个，对于不在这两棵子树内的双联通分量上的点均产生有贡献。然后就可以愉快的 \(O(n)\) 统计啦~
#include using namespace std;
#define int long long
#define maxn 500000
int N, n, m, tot, S[maxn], fa[maxn];
int timer, dfn[maxn], low[maxn];
int ans, size[maxn], cnt[maxn];
bool vis[maxn];
struct edge
{
int cnp = 1, head[maxn], to[maxn], last[maxn];
void add(int u, int v)
{
if(u == v) return;
to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++;
to[cnp] = u, last[cnp] = head[v], head[v] = cnp ++;
}
}E1, E2, E3;
int read()
{
int x = 0, k = 1;
char c;
c = getchar();
while(c ‘0‘ || c > ‘9‘) { if(c == ‘-‘) k = -1; c = getchar(); }
while(c >= ‘0‘ && c ‘9‘) x = x * 10 + c - ‘0‘, c = getchar();
return x * k;
}
void Tarjan(int u)
{
dfn[u] = low[u] = ++ timer; S[++ S[0]] = u;
for(int i = E1.head[u]; i; i = E1.last[i])
{
int v = E1.to[i];
if(!dfn[v])
{
Tarjan(v); low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u])
{
E2.add(++ N, u); cnt[N] ++, cnt[u] ++; int x = 0;
do
{
E2.add(N, x = S[S[0] --]); cnt[N] ++, cnt[x] ++;
}while(x != v);
}
}
else low[u] = min(low[u], dfn[v]);
}
}
void dfs(int u)
{
vis[u] = 1;
if(u ;
for(int i = E2.head[u]; i; i = E2.last[i])
{
int v = E2.to[i]; if(v == fa[u]) continue;
fa[v] = u; dfs(v); size[u] += size[v];
}
}
void DP(int u)
{
for(int i = E2.head[u]; i; i = E2.last[i])
{
int v = E2.to[i]; if(v == fa[u]) continue;
DP(v);
}
int tem = 0;
if(u n)
{
for(int i = E2.head[u]; i; i = E2.last[i])
{
int v = E2.to[i];
if(v != fa[u]) tem += (size[v]) * (tot - size[v] - 1);
else tem += (tot - size[u]) * (size[u] - 1);
}
}
else
{
if(cnt[u] > 2)
{
for(int i = E2.head[u]; i; i = E2.last[i])
{
int v = E2.to[i];
if(v != fa[u]) tem += (size[v]) * (tot - size[v]) * (cnt[u] - 2);
else tem += (tot - size[u]) * (size[u]) * (cnt[u] - 2);
}
}
}
ans += tem;
}
signed main()
{
N = n = read(), m = read();
for(int i = 1; i )
{
int u = read(), v = read();
E1.add(u, v);
}
for(int i = 1; i )
if(!dfn[i]) Tarjan(i);
for(int i = 1; i )
if(!vis[i])
{
dfs(i); tot = size[i];
DP(i);
}
printf("%lld\n", ans);
return 0;
}
【题解】APIO2018 Duathlon 铁人两项
标签：nbsp bit include col signed turn 匹配 中间 tchar
原文地址：https://www.cnblogs.com/twilight-sx/p/9241465.html
评论