bzoj1123&luogu3469 [POI2008]BLO-Blockade

bzoj1123&luogu3469 [POI2008]BLO-Blockade

​​ 题目描述

There are exactly nnn towns in Byteotia.

Some towns are connected by bidirectional roads.

There are no crossroads outside towns, though there may be bridges, tunnels and flyovers. Each pair of towns may be connected by at most one direct road. One can get from any town to any other-directly or indirectly.

Each town has exactly one citizen.

For that reason the citizens suffer from loneliness.

It turns out that each citizen would like to pay a visit to every other citizen (in his host’s hometown), and do it exactly once. So exactly n⋅(n−1)n\cdot (n-1)n⋅(n−1) visits should take place.

That’s right, should.

Unfortunately, a general strike of programmers, who demand an emergency purchase of software, is under way.

As an act of protest, the programmers plan to block one town of Byteotia, preventing entering it, leaving it, and even passing through.

As we speak, they are debating which town to choose so that the consequences are most severe.

Task Write a programme that:

reads the Byteotian road system’s description from the standard input, for each town determines, how many visits could take place if this town were not blocked by programmers, writes out the outcome to the standard output.

给定一张无向图，求每个点被封锁之后有多少个有序点对(x,y)(x!=y,1<=x,y<=n)满足x无法到达y

输入输出格式

输入格式：

In the first line of the standard input there are two positive integers: nnn and mmm (1≤n≤100 0001\le n\le 100\ 0001≤n≤100 000, 1≤m≤500 0001\le m\le 500\ 0001≤m≤500 000) denoting the number of towns and roads, respectively.

The towns are numbered from 1 to nnn.

The following mmm lines contain descriptions of the roads.

Each line contains two integers aaa and bbb (1≤a

#include#includeusing namespace std;#define N 110000#define M 550000inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}long long ans[N];struct node{ int y,next;}data[M<<1];int size[N],dfn[N],low[N],h[N],num,n,fa[N],m,dep[N];void tarjan(int x){ dfn[x]=low[x]=++num;int child=0;size[x]++;int z=0;ans[x]+=n-1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (fa[x]==y) continue; if (!dfn[y]){dep[y]=dep[x]+1; fa[y]=x;child++;tarjan(y);low[x]=min(low[x],low[y]); size[x]+=size[y]; if (fa[x]&&low[y]>=dfn[x]) { z+=size[y];ans[x]+=(long long)size[y]*(n-z-1); } }else low[x]=min(low[x],dfn[y]); } if (!fa[x]&&child>=2){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (fa[y]==x&&dep[y]-dep[x]==1){ for (int j=data[i].next;j;j=data[j].next){ int y1=data[j].y; if (dep[y1]-dep[x]==1)ans[x]+=(long long)size[y]*size[y1]; } } } }}int main(){ freopen("3469.in","r",stdin); n=read();m=read(); for (int i=1;i<=m;++i){ int x=read(),y=read(); data[++num].y=y;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].next=h[y];h[y]=num; }num=0;dep[1]=1; tarjan(1); for (int i=1;i<=n;++i) printf("%lld\n",ans[i]<<1); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。