hdu 4612 warm up 带重边的边bcc+缩点+树的直径

缘起

图论综合题. hdu 4612 warm up

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
一个无向连通图(有重边),允许加一条边,使得加边后的图割边最少,问加边后的最少割边数量.

【输入】
多样例. 首先输入的是N和M. 
2<=N<=200000, 1<=M<=1000000
然后是M行，表明边
输入以 0 0 结束

【输出】
每个样例输出答案

【样例输入】
4 4
1 2
1 3
1 4
2 3
0 0 

【样例输出】
0

【限制】
5s 65535KB

此题较为综合. 思路是跑tarjan之后，通过low数组进行缩点成为无向树. 最后两趟bfs（或者dfs）求出树的直径. 则减少的割边数量就是树的直径长度. 因为只需要将树的直径两头的边bcc相连即可让直径上的桥全部不是桥了.

所以最后的答案就是 割边的数量减去树的直径

所以本题是图论综合好题~

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
//#include "stdafx.h"
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>
#include <stack>
using namespace std;
//#define LOCAL

const int maxn = 200005;
int n,m, id, low[maxn], timestamp[maxn], t, cnt, res, ebccnum, belong[maxn]; // cnt是割边的数量

struct Edge
{
	int to, id;
	Edge(int to, int id):to(to),id(id){}
};
vector<Edge> g[maxn];
typedef vector<Edge>::iterator vit;
stack<int> s; // 收割边bcc要用的
void dfs(int cur, int fa)
{
	timestamp[cur] = low[cur] = ++t;
	s.push(cur);
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++)
	{
		if (!timestamp[x->to])
		{
			dfs(x->to, x->id);
			low[cur] = min(low[cur], low[x->to]);
			if (low[x->to]>timestamp[cur]) // 出现割边 x->to---cur
			{
				cnt++;
				ebccnum++; // 开始收割ebcc
				int j;
				do 
				{
					j = s.top();
					s.pop();
					belong[j] = ebccnum; // 这里其实可以开一个vector<int> ebcc 收集边bcc, 但就本题而言没必要
				} while (j!=x->to); // x->to 是不进栈的, 因为x->to是桥的另一头
			}
		}
		else if (x->id!=fa)
		{
			low[cur] = min(low[cur], timestamp[x->to]);
		}
	}
}

int head[maxn],num;
struct Arc
{
	int from, to, nxt;
}gg[2000005]; // gg 是缩点后构的图

void addArc(int a, int b)
{
	gg[num].from = a, gg[num].to = b, gg[num].nxt = head[a];
	head[a] = num++;
}

bool v[maxn];
int bfs(int i, int &ans) // 从i出发,找树的直径的一个端点, 并且ans就是最远的距离
{
	memset(v, 0, sizeof(v));
	ans = 0;
	int p; // _max是最远距离, p是实现最远距离的树的顶点
	struct Node
	{
		int to, dis;
		Node(int to, int dis):to(to),dis(dis){}
	};
	queue<Node> q;
	q.push(Node(i,0));
	v[i] = true;
	while(!q.empty())
	{
		Node front = q.front();
		q.pop();
		if (ans<front.dis)
		{
			ans = front.dis;
			p = front.to;
		}
		for (int h = head[front.to],to; ~h;  h = gg[h].nxt)
		{
			to = gg[h].to;
			if (!v[to])
			{
				v[to] = true;
				q.push(Node(to, front.dis+1));
			}
		}
	}
	return p;
}

void rebuild()
{
	memset(head, -1, sizeof(head));
	num = 0;
	for (int i = 1; i<=n;i++)
	{
		for (vit x = g[i].begin(); x!=g[i].end(); x++)
		{
			if (belong[i]!=belong[x->to])
			{
				addArc(belong[i], belong[x->to]); // 后面还会有的, 不需要反向加一次
			}
		}
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &n,&m),n||m)
	{
		id = t = cnt = 0;
		memset(low,0, sizeof(low));
		memset(timestamp, 0, sizeof(timestamp));
		for (int i = 1; i<=n;i++)
		{
			g[i].clear();
		}
		while(m--)
		{
			int a,b;
			scanf("%d%d", &a, &b);
			id++;
			g[a].push_back(Edge(b,id)), g[b].push_back(Edge(a, id));
		}
		ebccnum = 0;
		while(!s.empty())
		{
			s.pop();
		}
		memset(belong, 0, sizeof(belong));
		dfs(1,0); // 跑一边tarjan算法
		if (!ebccnum) // 如果原本所有的点都在一个边bcc中的话（因为上面跑tarjan的时候都没有出现过割边, 即上面第33行根本没进去过）
		{
			puts("0");
			continue;
		}
		ebccnum++; // 否则,说明出现了割边,上面33行代码有进去过
		for (int i = 1; i<=n;i++) // 收集最后的那个边bcc
		{
			if (!belong[i])
			{
				belong[i] = ebccnum;
			}
		}
		rebuild(); // 缩点构图(一棵无向树) 点的标号从1开始, 表示第一个边bcc
		int ans;
		int p = bfs(1, ans); // 第一趟bfs找树的直径的一个端点p
		bfs(p, ans); // 从p出发继续bfs, 得到树的直径的另一端, 并且ans变成树的直径.
		printf("%d\n", cnt-ans); // 割边的数量减去树的直径就是最少的剩余的割边数量
	}
	return 0;
}

ac情况（好吃内存~ 差点 MLE~）

Status Accepted
Time 1466ms
Memory 58120kB
Length 3129
Lang G++
Submitted 2019-09-11 09:38:34
RemoteRunId 30551198

这种综合题ac真心不容易啊~