P3469 [POI2008]BLO-Blockade 强连通

佚名 6年前 (2019-05-08) 随笔 1099人围观抢沙发百度已收录

题意翻译

题目描述

在Byteotia有n个城镇。一些城镇之间由无向边连接。在城镇外没有十字路口，尽管可能有桥，隧道或者高架公路（反正不考虑这些）。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。每个城镇都有一个公民，他们被孤独所困扰。事实证明，每个公民都想拜访其他所有公民一次（在主人所在的城镇）。所以，一共会有n*（n-1）次拜访。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

不幸的是，一个程序员总罢工正在进行中，那些程序员迫切要求购买某个软件。

作为抗议行动，程序员们计划封锁一些城镇，阻止人们进入，离开或者路过那里。

正如我们所说，他们正在讨论选择哪些城镇会导致最严重的后果。

编写一个程序：

读入Byteotia的道路系统，对于每个被决定的城镇，如果它被封锁，有多少访问不会发生，输出结果。

输入输出格式

第一行读入n，m，分别是城镇数目和道路数目

城镇编号1~n

接下来m行每行两个数字a,b，表示a和b之间有有一条无向边

输出n行，每行一个数字，为第i个城镇被锁时不能发生的访问的数量。

这题不用特判割点！！！想一想

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=100000+5;
const int M=1000000+5;
int head[M],pos;
struct Edge
{
    int to,nex;
}edge[M];
int n,m;
void add(int a,int b)
{
    edge[++pos].nex=head[a];
    head[a]=pos;
    edge[pos].to=b;
}
int tot,ind,cnt,dfn[N],low[N],sta[N],vis[N];
void init()
{
    tot=ind=cnt=0;
    CLR(dfn,0);
    CLR(low,0);
    CLR(sta,0);
    CLR(vis,0);
}
int siz[N];
ll ans[N];
void tarjan(int x)
{
    dfn[x]=low[x]=++tot;

    siz[x]=1;
    ll sum=0;//累积的
    for(int i=head[x];i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            siz[x]+=siz[v];
            if(low[v]>=dfn[x])//说明为割点
            {
                ans[x]+=siz[v]*sum;
                sum+=siz[v];
            }
            low[x]=min(low[x],low[v]);
        }
        else low[x]=min(low[x],dfn[v]);//这里一定要dfn
    }
    ans[x]+=(n-sum-1)*sum;//不要忘了剩下的点产生的贡献！
    ans[x]+=n-1;
}

int main()
{
    RII(n,m);
    rep(i,1,m)
    {
        int a,b;RII(a,b);
        add(a,b);
        add(b,a);
    }
    tarjan(1);
    rep(i,1,n)
        cout<<ans[i]*2<<endl;

    return 0;
}