tarjan强联通专题

自用笔记算法

tarjan强联通专题

模版

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
50
51
52
53
54
55
56
struct tarjan{
	const static int maxn=2e3+7;
	const static int maxm=1e6+7;
	struct Edge{
		int to,nxt;
		Edge(){}
		Edge(int t,int n):to(t),nxt(n){}
	}edge[maxm];
	int head[maxn],tot,n;
	int low[maxn],DFN[maxn],stack[maxn],belong[maxn];
	int index,top;
	int scc;
	int num[maxn];
	bool instack[maxn];
	inline void init(int n){
		tot=0;
		this->n=n;
		memset(head,-1,sizeof(head));
	}
	inline void addedge(int u,int v){
		edge[tot]=Edge(v,head[u]);
		head[u]=tot++;
	}
	void Tarjan(int u){
		int v;
		low[u]=DFN[u]=++index;
		stack[top++]=u;
		instack[u]=true;
		for(int i=head[u];~i;i=edge[i].nxt){
			v=edge[i].to;
			if(!DFN[v]){
				Tarjan(v);
				low[u]=min(low[u],low[v]);
			}
			else if(instack[v] && low[u]>DFN[v]) low[u]=DFN[v];
		}
		if(low[u]==DFN[u]){
			scc++;
			do{
				v=stack[--top];
				instack[v]=false;
				belong[v]=scc;
				num[scc]++;
			}while(v!=u);
		}
	}
	inline void find_scc(int n){
		memset(DFN,0,sizeof(DFN));
		memset(num,0,sizeof(num));
		memset(instack,0,sizeof(instack));
		index=scc=top=0;
		for(int i=1;i<=n;i++){
			if(!DFN[i]) Tarjan(i);
		}
	}
}g;

2017乌鲁木齐网赛

转跳链接

HDU 5934

题目要求

给你N个炸弹 对应已知其坐标和爆炸范围 以及引爆这个炸弹需要的花费 如果引爆了炸弹a b炸弹在a炸弹的作用范围之内 那么b炸弹也会被引爆 问将所有炸弹都引爆需要的最小花费
若圆a经过圆b的圆心 那么a会引爆b

参考AC代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
#define maxn 2050
#define maxm 2000050
#define inf 0x3f3f3f3f
#define LL long long
using namespace std;
int t,n;
struct node{
    LL x,y,r;
    int c;
}a[maxn];
struct tarjan{
    struct Edge{
        int to,nxt;
        Edge(){}
        Edge(int t,int n):to(t),nxt(n){}
    }edge[maxm];
    int head[maxn],tot,n;
    int low[maxn],DFN[maxn],stack[maxn],belong[maxn];
    int index,top;
    int scc;
    int num[maxn];
    bool instack[maxn];
    inline void init(int n){
        tot=0;
        this->n=n;
        memset(head,-1,sizeof(head));
    }
    inline void addedge(int u,int v){
        edge[tot]=Edge(v,head[u]);
        head[u]=tot++;
    }
    void Tarjan(int u){
        int v;
        low[u]=DFN[u]=++index;
        stack[top++]=u;
        instack[u]=true;
        for(int i=head[u];~i;i=edge[i].nxt){
            v=edge[i].to;
            if(!DFN[v]){
                Tarjan(v);
                low[u]=min(low[u],low[v]);
            }
            else if(instack[v] && low[u]>DFN[v]) low[u]=DFN[v];
        }
        if(low[u]==DFN[u]){
            scc++;
            do{
                v=stack[--top];
                instack[v]=false;
                belong[v]=scc;
                num[scc]++;
            }while(v!=u);
        }
    }
    int indeg[maxn],outdeg[maxn];
    inline int solve(int n){
        memset(DFN,0,sizeof(DFN));
        memset(num,0,sizeof(num));
        memset(instack,0,sizeof(instack));
        index=scc=top=0;
        for(int i=1;i<=n;i++){
            if(!DFN[i]) Tarjan(i);
        }
        memset(indeg,0,sizeof(indeg));
        memset(outdeg,0,sizeof(outdeg));
        for(int u=1;u<=n;u++){
            for(int i=head[u];i!=-1;i=edge[i].nxt){
                int v=edge[i].to;
                if(belong[u]!=belong[v]){
                    outdeg[belong[u]]++;
                    indeg[belong[v]]++;
                }
            }
        }
        int ans=0;
        for(int i=1;i<=scc;i++){
            if(indeg[i]==0){
                int temp=inf;
                for(int j=1;j<=n;j++){
                    if(belong[j]==i) temp=min(temp,a[j].c);
                }
                ans+=temp;
            }
        } 
        return ans;
    }
}g;
bool check(int i,int j){
    if(a[i].r*a[i].r>=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)) return true;
    return false;
}
int Case=1;
int main(){
//    freopen("input.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        g.init(n);
        for(int i=1;i<=n;i++) scanf("%lld%lld%lld%d",&a[i].x,&a[i].y,&a[i].r,&a[i].c);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) continue;
                if(check(i,j)) g.addedge(i,j);
            }
        }
        printf("Case #%d: %d\n",Case++,g.solve(n));
    }
    return 0;
}

思路

注意判断圆是否经过另一个圆的圆心的check函数写法
建图：如果a能引爆b 那么a向b连一条边
用tarjan缩点
计算缩点后以连通分量为单位点的出入度
把所有入度为0的连通分量里求出最小花费 加到ans上
所有入度大于0的点必须由别的点引爆 因为他不能引爆别人 所以会额外增加花费 根据策略分析这些点必须跳过由别的点引爆

uva 11324

题目要求

白书P323

参考AC代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
#define maxn 1050
#define maxm 50050
#define inf 0x3f3f3f3f
#define LL long long
using namespace std;
int t,n,m;
struct tarjan{
    struct Edge{
        int to,nxt;
        Edge(){}
        Edge(int t,int n):to(t),nxt(n){}
    }edge[maxm];
    int head[maxn],tot,n;
    int low[maxn],DFN[maxn],stack[maxn],belong[maxn];
    int index,top;
    int scc;
    int num[maxn];
    bool instack[maxn];
    inline void init(int n){
        tot=0;
        this->n=n;
        memset(head,-1,sizeof(head));
    }
    inline void addedge(int u,int v){
        edge[tot]=Edge(v,head[u]);
        head[u]=tot++;
    }
    void Tarjan(int u){
        int v;
        low[u]=DFN[u]=++index;
        stack[top++]=u;
        instack[u]=true;
        for(int i=head[u];~i;i=edge[i].nxt){
            v=edge[i].to;
            if(!DFN[v]){
                Tarjan(v);
                low[u]=min(low[u],low[v]);
            }
            else if(instack[v] && low[u]>DFN[v]) low[u]=DFN[v];
        }
        if(low[u]==DFN[u]){
            scc++;
            do{
                v=stack[--top];
                instack[v]=false;
                belong[v]=scc;
                num[scc]++;
            }while(v!=u);
        }
    }
    inline void find_scc(){
        memset(DFN,0,sizeof(DFN));
        memset(num,0,sizeof(num));
        memset(instack,0,sizeof(instack));
        index=scc=top=0;
        for(int i=1;i<=n;i++){
            if(!DFN[i]) Tarjan(i);
        }
    }
    int size[maxn],mp[maxn][maxn],dp[maxn];
    int dfs(int x){
    	if(dp[x]!=-1) return dp[x];
    	int ans=size[x];
    	for(int i=1;i<=scc;i++){
    		if(i!=x && mp[x][i]) ans=max(ans,dfs(i)+size[x]);
		}
		return dp[x]=ans;
	}
	int solve(){
    	int ans=0;
    	memset(size,0,sizeof(size));
    	memset(mp,0,sizeof(mp));
    	memset(dp,-1,sizeof(dp));
    	for(int i=1;i<=n;i++){
    		size[belong[i]]++;
    		for(int j=head[i];j!=-1;j=edge[j].nxt){
    			int x=edge[j].to;
    			mp[belong[i]][belong[x]]=1;
			}
		}
		for(int i=1;i<=scc;i++){
			ans=max(ans,dfs(i));
		}
		return ans;
	} 
}g;
int main(){
//	freopen("input.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        g.init(n);
		for(int i=1;i<=m;i++){
        	int u,v;
        	scanf("%d%d",&u,&v);
        	g.addedge(u,v);
		}
		g.find_scc();
		printf("%d\n",g.solve());
    }
    return 0;
}

思路

白书P323
缩点后size计算每个连通分量里点的个数
对scc建新图
相当于求新图可以走到的最大路径 记忆化dp搜索即可

本文标题:tarjan强联通专题

文章作者:Hippopmonkey

发布时间:2017-10-26, 23:47:30

最后更新:2017-10-27, 00:06:02

原始链接:http://xuboming8.github.io/2017/10/26/tarjan强联通专题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. tarjan强联通专题
    1. 1.1. 模版
    2. 1.2. 2017乌鲁木齐网赛
    3. 1.3. HDU 5934
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. uva 11324
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
|