UOJ #270 电厂计划

【题目描述】:

停电,漆黑的夜晚。

ACM + +是一家电力公司。该公司拥有数个发电厂,每一个供应一个小面积,这些发电厂给这个公司带来了很多的麻烦,在某些地区没有足够的电力,而在其他地区却有大量的盈余。

ACM ++因此决定将一些发电厂连接成一个网络。当然第一阶段,没有必要将所有的发电厂连接到一个网络,但另一方面,它必须在关键地方建立冗余连接,即网络不保证是连通的。现在提出了各种连接的计划,并已开始复杂的评估。

必须考虑的评估标准之一是创建的网络的可靠性。我们假设可以发生的最坏的事件是一个发电厂故障,这可能会导致网络分成几个部分。虽然每一部分都可以工作,但被分成的部分越多,麻烦可能性就越大。因此,我们必须找出所有方案中,某个电厂故障,会形成的最大块数。
【输入描述】:

输入由若干实例组成。

每个实例第一行都包含两个整数P和C(1 <= P = 10,000,C >= 0),中间用空格隔开。P是电厂的数量。电厂编号为0到P - 1之间的整数。C是边数。下面的C行,每一行包含两个整数0 < = P1,P2<P用一个空格隔开,这意味着电厂P1和P2连接。每个连接不会重复描述。输入终止的行包含两个零。
【输出描述】:

输出由若干行组成。输出的第i行对应于第i个输入实例。输出的每一行由一个整数组成,即通过在实例中删除一个连接点,最多可以使网络分成的最大块数。
【样例输入】:

3 3
0 1
0 2
2 1
4 2
0 1
2 3
3 1
1 0
0 0

【样例输出】:

1
2
2

【时间限制、数据范围及描述】:

时间:1s 空间:64M

1 <= P = 10,000

注意没有边的情况

这里就是统计当删除每一个割点,能使整个连通图所分成的最大块数。

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=1000005;
int t,cnt,head[N],son[N],dfn[N],low[N],n,ans[N],m,tot,maxn;
bool is_ok[N];
struct Node{
    int u,v,next;
}edge[N];
void push(int u,int v){
    ++cnt;
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
void tarjan(int v,int u){
    low[v]=dfn[v]=++t;
    for(int i=head[v];i!=-1;i=edge[i].next){
        int v1=edge[i].v;
        if(v1==u){
            continue;
        }
        if(dfn[v1]==0){
            tarjan(v1,v);
            low[v]=min(low[v],low[v1]);
            if(low[v1]>=dfn[v]){
                ans[v]++;
            }
        }
        else{
            low[v]=min(low[v],dfn[v1]);
        }
    }
}
int main(){
    while(scanf("%d%d",&n,&m)){
        if(n==0&&m==0){
            break;
        }
        tot=0;
        maxn=-1;
        cnt=0;
        t=0;
        memset(head,-1,sizeof(head));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(is_ok,false,sizeof(is_ok));
        memset(ans,0,sizeof(ans));
        int u,v;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            push(u+1,v+1);
            push(v+1,u+1);
        }
        for(int i=1;i<=n;i++){
            if(dfn[i]==0){
                tot++;
                ans[i]=-1;
                tarjan(i,-1);
            }
        }
        for(int i=1;i<=n;i++){
            maxn=max(maxn,ans[i]);
        }
        printf("%d\n",tot+maxn);
    }
    return 0;
}
上一篇:基于texlive定制chemfig化学式转换Python服务镜像


下一篇:PHP 安全三板斧:过滤、验证和转义之转义篇 & Blade模板引擎避免XSS攻击原理探究