M_sea

洛谷3225 [HNOI2012]矿场搭建
题目描述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条...
扫描右侧二维码阅读全文
23
2018/08

洛谷3225 [HNOI2012]矿场搭建

题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。

传送门

算法

感觉像割点

考虑Tarjan求割点。可以发现,在一个双联通分量中,设割点的数目为$s_1$,非割点的数目为$s_2$,那么:

  • 若$s_1=0$,即没有割点,那么要有两个出口才能保证能出去。此时出口可以放在任意两个非割点上。
  • 若$s_1=1$,即只有一个割点,那么如果割点坍塌就都出不去了,所以要放一个出口。此时出口可以放在任意一个非割点上。注意到这里若非割点坍塌,其它点可以通过割点离开到其它分量去。
  • 若$s_1>1$,即有大于一个割点,那么无论哪个点坍塌,其它点都可以到别的分量去。此时不用设置出口。

细节见代码。

然而我这个菜鸡因为少写了vis[v]=dfs_time而卡了0.5h qwq

代码

#include <bits/stdc++.h>
#define re register
#define max_(a,b) ((a)>(b)?(a):(b))
#define min_(a,b) ((a)<(b)?(a):(b))
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m;

struct Edge { int v,nxt; };
Edge e[1010];
int head[510],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int dfn[510],low[510],dfs_clock=0;
int cut[510];

inline void Tarjan(int u,const int root) {
    dfn[u]=low[u]=++dfs_clock; int f=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) {
            Tarjan(v,root);
            low[u]=min_(low[u],low[v]);
            if (low[v]>=dfn[u]) {
                f++;
                if (u!=root||f>1) cut[u]=1;
            }
        }
        else low[u]=min_(low[u],dfn[v]);
    }
}

int vis[510],dfs_time=0;
int sc=0,snc=0; //割点数、非割点数 

inline void Dfs(int u) {
    vis[u]=dfs_time,++snc;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (vis[v]==dfs_time) continue;
        if (cut[v]) ++sc,vis[v]=dfs_time;
        else Dfs(v);
    }
}

mainint main() {
    int T=0;
    while ((m=read())) { //这个括号是因为C++11的编译器Warning,看着不爽就加上了
        if (!m) break;
        
        n=cnt=dfs_time=dfs_clock=0;
        memset(vis,0,sizeof(vis));
        memset(dfn,0,sizeof(vis));
        memset(low,0,sizeof(vis));
        memset(head,0,sizeof(head));
        memset(cut,0,sizeof(head));
        
        for (re int i=1;i<=m;++i) {
            int x=read(),y=read();
            addEdge(x,y);
            addEdge(y,x);
            n=max_(n,max_(x,y));
        }
        
        for (re int i=1;i<=n;++i)
            if (!dfn[i]) Tarjan(i,i);
        
        int ans1=0,ans2=1;
        for (re int i=1;i<=n;++i) {
            if (vis[i]||cut[i]) continue;
            ++dfs_time,sc=0,snc=0;
            Dfs(i);
            if (!sc) ans1+=2,ans2*=snc*(snc-1)/2;
            else if (sc==1) ++ans1,ans2*=snc;
        }
        printf("Case %lld: %lld %lld\n",++T,ans1,ans2);
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 21 PM

发表评论