首页 > 代码库 > BZOJ1123: [POI2008]BLO
BZOJ1123: [POI2008]BLO
1123: [POI2008]BLO
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 614 Solved: 235
[Submit][Status]
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
题解：
这题应该是裸的求割点，但应该我还不会，所以去学习了一下。。。
道理很简单，上篇博文里讲的很清楚。
hzwer关于此题的题解：
把某个割点去掉以后，会出现几个连通块，它们之间不能互相到达
即会分成上面一棵树，下面若干子树
子树之间不互通，所有子树和上面那个树不互通，通过记录树的大小统计答案
另外删去的点和其它点不互通
------------------------------------------
应该是显然的吧。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 100000+1000 26 27 #define maxm 500000+1000 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int head[maxn],low[maxn],dfn[maxn],ti,n,m,tot; 61 ll s[maxn],ans[maxn]; 62 struct edge{int go,next;}e[2*maxm]; 63 inline void insert(int x,int y) 64 { 65 e[++tot].go=y;e[tot].next=head[x];head[x]=tot; 66 e[++tot].go=x;e[tot].next=head[y];head[y]=tot; 67 } 68 inline void dfs(int x) 69 { 70 ll t=0; 71 s[x]=1; 72 low[x]=dfn[x]=++ti; 73 for(int i=head[x],y;i;i=e[i].next) 74 if(!dfn[y=e[i].go]) 75 { 76 dfs(y); 77 s[x]+=s[y]; 78 low[x]=min(low[x],low[y]); 79 if(low[y]>=dfn[x]) 80 { 81 ans[x]+=t*s[y]; 82 t+=s[y]; 83 } 84 } 85 else low[x]=min(low[x],dfn[y]); 86 ans[x]+=t*(n-t-1); 87 } 88 89 int main() 90 91 { 92 93 freopen("input.txt","r",stdin); 94 95 freopen("output.txt","w",stdout); 96 97 n=read();m=read(); 98 for1(i,m)insert(read(),read()); 99 dfs(1);100 for1(i,n)printf("%lld\n",(ans[i]+n-1)*2);101 102 return 0;103 104 }
BZOJ1123: [POI2008]BLO
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。