【bzoj1123】BLO
2024-09-04 17:32:02
1123: [POI2008]BLO
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2222 Solved: 1090
[Submit][Status][Discuss]
Description
Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。
Input
输入n<=100000 m<=500000及m条边
Output
输出n个数,代表如果把第i个点去掉,将有多少对点不能互通。
Sample Input
5 5
1 2
2 3
1 3
3 4
4 5
1 2
2 3
1 3
3 4
4 5
Sample Output
8
8
16
14
8
8
16
14
8
HINT
Source
题意:
极其简洁啊……
题解:
缩完点双后原图会变为一棵树。
每删掉一个割点,它的子树之间两两不能连接,子树与子树外的点两两不能连接。
然后惊奇的发现这题的点对要算上被删去的那个点。GG。
代码:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> using namespace std;
#define MAXN 100005
#define MAXM 500005
#define INF 0x7fffffff
#define ll long long ll hd[MAXN],to[MAXM<<];
ll nxt[MAXM<<],siz[MAXN];
ll dfn[MAXN],low[MAXN];
ll N,M,ans[MAXN],cnt,num; inline ll read(){
ll x=,f=;
char c=getchar();
for(;!isdigit(c);c=getchar())
if(c=='-')
f=-;
for(;isdigit(c);c=getchar())
x=x*+c-'';
return x*f;
} inline void tarjan(ll u){
dfn[u]=low[u]=++num;
ll cutnum=;siz[u]=;
for(ll i=hd[u];i;i=nxt[i]){
ll v=to[i];
if(dfn[v]) low[u]=min(low[u],dfn[v]);
else{
tarjan(v);siz[u]+=siz[v];
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
ans[u]+=(cutnum*siz[v]);
cutnum+=siz[v];
}
}
}
ans[u]+=(cutnum*(N-cutnum-));
return;
} inline void addedge(ll u,ll v){
to[++cnt]=v,nxt[cnt]=hd[u];
hd[u]=cnt;return;
} int main(){
N=read(),M=read();
for(ll i=;i<=M;i++){
ll u=read(),v=read();
addedge(u,v),addedge(v,u);
}
for(ll i=;i<=N;i++)
if(!dfn[i])
tarjan(i);
for(ll i=;i<=N;i++)
printf("%lld\n",ans[i]*+(N-)*);
return ;
}
最新文章
- [asp.net core] Tag Helpers 简介(转)
- EF架构~为EF DbContext生成的实体添加注释(T5模板应用)
- POJ2699 The Maximum Number of Strong Kings
- [第三方]AFNetWorking3.0网络框架使用方法
- kernel/panic.c
- Spring3系列10- Spring AOP——Pointcut,Advisor拦截指定方法
- ArcGIS Add-in——自动保存编辑
- LeetCode 101. Symmetric Tree
- IDEA 创建Web项目并在Tomcat中部署运行
- java命令行运行jar里的main类
- 数据结构——foodfill 八连块问题
- SQL 2008存储图片和读取图片
- Java日志工具之java.util.logging.Logger
- POJ 3923 Ugly Windows(——考察思维缜密性的模拟题)
- List实现
- Velocity 语法及其在springMVC中的配置
- MAC上有哪些优秀的日常软件| 入门级Mac OS 用户必备软件
- Python数据科学“冷门”库
- 【重磅】Spring Boot 2.1.0 权威发布
- JavaScript学习-3——数组、函数、递归
热门文章
- JavaScript学习第三天
- UVA10655 Contemplation! Algebra —— 推公式、矩阵快速幂
- 第二篇:python基础之核心风格
- Notepad++安装xml插件
- Hihocoder 1625 : 重复字符串匹配 (KMP)
- 中缀表达式std
- python与c#的交互模块pythonnet
- Java编程环境eclipse配置
- webix前端架构的项目应用(项目框架为Web API+autofac+ioc+mysql+webix)
- ThinkPHP3.2.3中,查询语句中in的使用方法。