BZOJ2730: [HNOI2012]矿场搭建【tarjan求割点】

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

很容易的想到如果是割点塌掉的情况。

如果这个割点把整张图分裂了，那么就要保证每块里面都要装一个救援出口。

所以可以 这样做，先求出割点。然后dfs剩下的块。如果一个块只连接到了一个割点，那么这个块里面要有一个救援出口。否则就不用了。

如果没割点的话，要两个出口。不然有可能出口塌了= =。

?
BZOJ2730
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int p[50010],n1[50010],h[10010],v[10010],dfn[10010],low[10010],b[10010];
int s[50010],c[50010],tmp[50010],m,n,ee,tot,col;long long An1,An2;
void ae(int a,int b){
    p[ee]=b;    n1[ee]=h[a];    h[a]=ee++;
}void dfs(int u){
    v[u]=1;dfn[u]=low[u]=++tot;
    for(int i=h[u];~i;i=n1[i])  if(!v[p[i]]){
        dfs(p[i]);
        low[u]=min(low[u],low[p[i]]);
        if(low[p[i]]>=dfn[u])    b[u]++;
    }else   low[u]=min(low[u],dfn[p[i]]);
}void dfs2(int u){
    v[u]=1,s[col]++;
    for(int i=h[u];~i;i=n1[i])  if(!v[p[i]]){
        if(!b[p[i]])    dfs2(p[i]);
        else    if(c[p[i]]!=col)    c[p[i]]=col,tmp[col]++;
    }
}void init(){
    memset(h,-1,sizeof(h));
    memset(v,0,sizeof(v));
    memset(b,0,sizeof(b));
    memset(v,0,sizeof(v));
    memset(c,0,sizeof(c));
    memset(s,0,sizeof(s));
    memset(tmp,0,sizeof(tmp));
    n=ee=tot=col=An1=0;An2=1;
}int main(){
    int tc=0;
    while(scanf("%d",&m),m){
        int x,y;init();
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            ae(x,y);ae(y,x);
            n=max(n,max(x,y));
        }for(int i=1;i<=n;i++)   if(!v[i]){
            dfs(i);b[i]--;
        }memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++)    if(!v[i]&&!b[i]){
            col++;dfs2(i);
            if(tmp[col]==1) An1++,An2*=1ll*s[col];
        }if(col==1) An1=2,An2=1ll*n*(n-1)>>1;
        printf("Case %d: %lld %lld\n",++tc,An1,An2);
    }return 0;
}

BZOJ BZOJ tarjan Comments(0) 2013年8月08日 16:39

POJ1523 SPF 【Tarjan求割点】

理论知识看了好久的说、这里就不写了、

主要的是定义low[u]表示从u或u的子孙出发通过回边可以到达的最低深度优先数dfn[]。

low[u]=min{dfn[u], min{low[w]|w是u的子女}, min{dfn[v]|v与u邻接，且(u,v)是一条回边} }

?
POJ1523
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int low[2010],dfn[2010],ss[1010],v[1010],p[2010],n1[2010],h[1010],n,e=0,tot=0;
inline void ae(int a,int b){ p[e]=b; n1[e]=h[a]; h[a]=e++;}
void dfs(int u){
    for(int i=h[u];~i;i=n1[i]) if(!v[p[i]]){
        v[p[i]]=1;
        dfn[p[i]]=low[p[i]]=++tot;
        dfs(p[i]);
        low[u]=min(low[u],low[p[i]]);
        if(low[p[i]]>=dfn[u]) ss[u]++;
    }else low[u]=min(low[u],dfn[p[i]]);
}inline void init(){
    memset(h,-1,sizeof(h));
    memset(v,0,sizeof(v));
    memset(ss,0,sizeof(ss));
    e=0;tot=dfn[1]=low[1]=v[1]=1;
}int main(){
    int u,v,Tc=0;
    while(scanf("%d",&u),u){
        init();
        scanf("%d",&v);
        ae(u,v); ae(v,u);
        n=max(u,v);
        while(scanf("%d",&u),u){
            scanf("%d",&v);
            n=max(n,max(u,v));
            ae(u,v); ae(v,u);
        }dfs(1);
        if(Tc) printf("\n");
        printf("Network #%d\n",++Tc);
        int f=0;
        if(ss[1]>=1) ss[1]--;
        for(int i=1;i<=n;i++) if(ss[i]){
            f=1;
            printf("  SPF node %d leaves %d subnets\n",i,ss[i]+1);
        }if(!f) printf("  No SPF nodes\n");
    }return 0;
}

 

POJ POJ tarjan Comments(0) 2013年6月30日 14:32