GGAutomaton's Blog
0%

发表于 分类于 ， 
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
void dfs(int x,int ef) {
    int son=0;
    f[x]=true;
    low[x]=d[x]=++Time;
    for (int e=head[x];e!=-1;e=next[e]) {
        if (e==(ef^1)) continue;//针对无向图，而且重边算作多条边
        if (!f[vet[e]]) {
            dfs(vet[e],e);
            low[x]=min(low[x],low[vet[e]]);
            if (x!=root && d[x]<=low[vet[e]]) cut[x]++;//x为割点
            if (low[vet[e]]>d[x]) bridge[e/2]=true;//此边为桥
            son++;
        }
        else low[x]=min(low[x],d[vet[e]]);
    }
    if (x==root && son>1) cut[x]=son-1;//x为割点，注意-1
}


    num=-1;//边从0开始计数
    memset(head,-1,sizeof(head));
    
    
    for (int i=1;i<=n;i++)
        if (!f[i]) {
            root=i;
            dfs(i,-1);
        }
        
        
    for (int i=1;i<=n;i++)
        if (cut[i]!=0) 
            cout<< i << " " << cut[i]+1 << endl;//输出删去该点后分离出的子图个数，注意+1
    for (int i=0;m>i;i++)
        if (bridge[i]) 
            cout<< vet[i*2] << " " << vet[i*2+1] << endl;

发表于 分类于 ， 
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
int find(int x) {
    if (x != fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void lca(int x) {
    fa[x]=x;
    f[x]=1;
    a[x].d=++Time;
    for (int e=head[x];e!=0;e=next[e]) {
        if (f[vet[e]]==0) {
            len[vet[e]]=len[x]+val[e];//计算到根节点长度
            lca(vet[e]);
            fa[vet[e]]=x;
        }
    }
    a[x].f=++Time;
    f[x]=2;
    for (int e=headq[x];e!=0;e=nextq[e])
        if (f[vetq[e]]==2) {
            int v=find(vetq[e]);//v为最近公共祖先
            if (a[x].f<=a[v].f || a[v].f==0)
                ans[e]=len[x]+len[vetq[e]]-2*len[v];//计算编号为e的询问
            else ans[e]=-1;
        }
}

//主程序中先将询问双向建边

发表于 分类于 ，

【题目描述】

Ignatius 再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)…… 这次魔王汲取了上次的教训，把 Ignatius 关在一个 n*m 的地牢里，并在地牢的 某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始 Ignatius 被 关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius 每分钟只能从 一个坐标走到相邻四个坐标中的其中一个。魔王每 t 分钟回地牢视察一次，若发 现 Ignatius 不在原位置便把他拎回去。经过若干次的尝试，Ignatius 已画出整 个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前 走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口都算逃 亡失败。

【输入】

每组测试数据的第一行有三个整数 n,m,t(2<=n,m<=20,t>0)。接下来的 n 行 m列 为地牢的地图，其中包括:
. 代表路
* 代表墙
@ 代表 Ignatius 的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为 a-j
a-j 代表钥匙，对应的门分别为 A-J
每组测试数据之间有一个空行。

【输出】

针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开， 如果不能则输出-1。

【样例输入】

1
2
3
4
5
4 5 17
@A.B.
a*.*.
*..*^
c..b*

【样例输出】

16

【样例输入】

1
2
3
4
5
4 5 16
@A.B.
a*.*.
*..*^
c..b*

【样例输出】

-1

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
#include<bits/stdc++.h>
using namespace std;
int n,m,t,sx,sy,ex,ey;
int door[25][25],key[25][25];
bool map[25][25],vis[25][25][1024];
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
struct node {
    int x,y,stat,time;
};
bool judgedoor(int x,int y,int stat) {
    if (door[x][y]==0) return true;
    if ((stat&(1 << door[x][y]-1))==0) return false;
    else return true;
}
bool judge(int x,int y,int stat) {
    if (judgedoor(x,y,stat) && !vis[x][y][stat]) return true;
    return false;
}
int bfs() {
    queue q;
    while (!q.empty()) q.pop();
    node now,next;
    now.x=sx;now.y=sy;
    now.time=0;now.stat=0;
    q.push(now);
    vis[sx][sy][0]=true;
    while (!q.empty()) {
        now=q.front();
        q.pop();
        if (now.time==t) return -1;
        if (now.x==ex && now.y==ey) return now.time;
        for (int i=0;i<4;i++) {
            next.x=now.x+dx[i];
            next.y=now.y+dy[i];
            next.time=now.time+1;
            next.stat=now.stat;
            if (next.x>=1 && next.x<=n && next.y>=1 && next.y<=m && map[next.x][next.y]) {
                if (key[next.x][next.y]!=0) {
                    next.stat=next.stat|(1 << key[next.x][next.y]-1);
                    vis[next.x][next.y][next.stat]=true;
                    q.push(next);
                }
                else if (judge(next.x,next.y,next.stat)) {
                    vis[next.x][next.y][next.stat]=true;
                    q.push(next);
                }
            }
        }
    }
    return -1;
}
int main() {
    while (scanf("%d%d%d",&n,&m,&t)!=EOF) {
        char ch;
        memset(map,0,sizeof(map));
        memset(door,0,sizeof(door));
        memset(key,0,sizeof(key));
        memset(vis,0,sizeof(vis));
        for (int i=1;i<=n;i++) {
            ch=getchar();
            for (int j=1;j<=m;j++) {
                ch=getchar();
                if (ch!='*') map[i][j]=true;
                if (ch=='@') sx=i,sy=j;
                if (ch=='^') ex=i,ey=j;
                if (ch>='A' && ch<='J') door[i][j]=ch-'A'+1;
                if (ch>='a' && ch<='j') key[i][j]=ch-'a'+1;
            }
        }
        int ans=bfs();
        printf("%d\n",ans);
    }
    return 0;
}

发表于 分类于 ，

路径压缩： 

1
2
3
4
5
6
7
8
int find(int x) {
    if (x != fa[x]) {
        int tmp=fa[x];
        fa[x]=find(fa[x]);
        d[x]=(d[x]+d[tmp])%2;//自定义边权压缩
    }
    return fa[x];
}

按秩合并（无序）： 

1
2
3
4
5
6
7
8
void Union(int x,int y) {
    int rootx=find(x),rooty=find(y);
    if (rank[x]>rank[y]) fa[rooty]=x;
    else {
        fa[rootx]=y;
        if (rank[x]==rank[y]) rank[y]++;
    }
}

发表于 分类于 ，

不带堆优化，时间复杂度\(\ O(V^2)\)

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
#include<iostream>
#include<cstdio>
#include<climits>
int head[105],vet[10005],w[10005],next[10005],num;
int dist[105];
bool f[105];
void addedge(int x,int y,int c) {
	num++;
	vet[num]=y;
	w[num]=c;
	next[num]=head[x];
	head[x]=num;
}
int main() {
	int n,m,ans=0;
	std::cin >> n >> m;
	for (int i=1;i<=m;i++) {
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		addedge(x,y,c);
		addedge(y,x,c);
	}
	for (int i=1;i<=n;i++) dist[i]=INT_MAX;
	dist[1]=0;
	for (int i=1;i<=n;i++) {
		int mindist=INT_MAX,p=0;
		for (int j=1;j<=n;j++)
			if (!f[j] && mindist>dist[j]) {
				mindist=dist[j];
				p=j;
			}
		f[p]=true;
		ans+=dist[p];
		for (int e=head[p];e!=0;e=next[e])
			if (!f[vet[e]])
				dist[vet[e]]=std::min(dist[vet[e]],w[e]);
	}
	std::cout << ans;
	return 0;
}

堆优化，时间复杂度\(\ O(ElogE)\)
priority_queue实现：

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
#include<iostream>
#include<cstdio>
#include<climits>
#include<queue>
struct node {
	int p,weight;
	bool operator<(const node &a)const {
		return weight>a.weight;
	}
};
int head[100005],vet[200005],w[200005],next[200005],num;
int dist[100000];
bool f[100005];
void addedge(int x,int y,int c) {
	num++;
	vet[num]=y;
	w[num]=c;
	next[num]=head[x];
	head[x]=num;
}
int main() {
	int n,m;
	int ans=0;
	std::cin >> n >> m;
	for (int i=1;i<=m;i++) {
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		addedge(x,y,c);
		addedge(y,x,c);
	}
	for (int i=1;i<=n;i++) dist[i]=INT_MAX;
	dist[1]=0;
	std::priority_queue<node> qu;
	node newnode;
	newnode.weight=0;
	newnode.p=1;
	while (!qu.empty()) qu.pop();
	qu.push(newnode);
	for (int i=1;i<=n;i++) {
		while (f[qu.top().p]) qu.pop();
		newnode=qu.top();
		qu.pop();
		f[newnode.p]=true;
		ans+=newnode.weight;
		for (int e=head[newnode.p];e!=0;e=next[e])
			if (!f[vet[e]] && dist[vet[e]]>w[e]) {
				newnode.p=vet[e];
				newnode.weight=w[e];
				dist[vet[e]]=w[e];
				qu.push(newnode);
			}
	}
	std::cout << ans;
	return 0;
}

反向映射堆：

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
#include<iostream>
#include<cstdio>
#include<climits>
struct node {
    int p,weight;
    bool operator<(const node &a)const {
        return weight<a.weight;
    }
};
int head[100005],vet[200005],w[200005],next[200005],num;
int dist[100005],hsize,po[100005];
node heap[200005];
bool f[100005];
void addedge(int x,int y,int c) {
    num++;
    vet[num]=y;
    w[num]=c;
    next[num]=head[x];
    head[x]=num;
}
void sw(int p1,int p2) {
	po[heap[p1].p]=p2;
	po[heap[p2].p]=p1;
	node tmp=heap[p1];
	heap[p1]=heap[p2];
	heap[p2]=tmp;
}
void Up(int p) {
	while (p>1) {
		if (heap[p]<heap[p/2]) {
			sw(p,p/2);
			p/=2;
		}
		else break;
	}
}
void Down(int p) {
	while (p*2<=hsize) {
		int Min=p;
		if (heap[p*2]<heap[Min]) Min=p*2;
		if (p*2<hsize && heap[p*2+1]<heap[Min]) Min=p*2+1;
		if (Min != p) {
			sw(p,Min);
			p=Min;
		}
		else break;
	}
}
void decrease_key(int t,int v) {
	heap[t].weight=v;
	Up(t);
}
void heap_push(node res) {
	heap[++hsize]=res;
	po[res.p]=hsize;
	Up(hsize);
}
node heap_pop() {
	sw(1,hsize);
	hsize--;
	Down(1);
	po[heap[hsize+1].p]=0;
	return heap[hsize+1];
}
int main() {
    int n,m;
    int ans=0;
    std::cin >> n >> m;
    for (int i=1;i<=m;i++) {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        addedge(x,y,c);
        addedge(y,x,c);
    }
    for (int i=1;i<=n;i++) dist[i]=INT_MAX;
    dist[1]=0;
    heap_push((node){1,0});
    for (int i=1;i<=n;i++) {
        node newnode=heap_pop();
        f[newnode.p]=true;
        ans+=newnode.weight;
        for (int e=head[newnode.p];e!=0;e=next[e])
            if (!f[vet[e]] && dist[vet[e]]>w[e]) {
            	if (po[vet[e]]==0) heap_push((node){vet[e],w[e]});
            	decrease_key(po[vet[e]],w[e]);
                dist[vet[e]]=w[e];
            }
    }
    std::cout << ans;
    return 0;
}