HDU 5639 Deletion(网络流)

题目大意

给出一个 $n$ 个点 $m$ 条边的无向图 $G$,每次你可以选择一些边,从图中删掉。要求选出来的边构成的子图的每个连通块最多只有一个环。 问最少需要删几次才能把所有边都删掉。

$(1 \leq n \leq 2000, 0 \leq m \leq 2000)$

解题思路

网络流

官方题解:

方法一:
考虑删掉的边的形态,就是我们经常见到的环套树这种结构,参考平时这种图给出的方法,如果一个图的每个点的出边只有一条,那么一定会构成环套树这种结构。于是问题可以转化成,给无向图的每条边定向,使得出度最大点的出度最小 (每个点的出度大小对应了删的次数)。

显然,这个东西使可以二分的,不妨设二分值为 $x$。考虑混合图的欧拉回路的做法,利用网络流判合法。先给每条无向边随便定向,对于出度大于 $x$ 的,从源点连一条流量为 $deg-x$ 的边,对于出度小于 $x$ 的,从这个点连一条流量为 $x-deg$ 的边到汇点。对于原来图中的边,流量为 $1$ 加到网络流图中。只要满流就是合法。

方法二:
类似方法一,要求的无非是每条边的归属问题,对于每条边 $(a,b)$,它可以属于 $a$ 或者 $b$,那么新建一个节点表示这条边,并和 $a$,$b$ 都相邻,这样就得到了一个二分图。左边是原图中的节点,右边是原图中的边。二分每个左边每个节点的容量 $k$,如果右边的点能够完全匹配,那么这个 $k$ 就是可行的,找到最小的 $k$ 即可。转化成二分图多重匹配问题。

方法三:
事实上这题存在 $O(nm)$ 的做法,只要在方法二的基础上继续改进就好了,二分是没有必要的。注意到每次增广的时候,增光路中只有端点的容量会变化,增广路中间的点的容量都不会变化。那么之要每次增广到端点容量最小的那个点就好了。

感觉题目很不错,所以虽然代码是照着题解写的,但还是放上来了。特别是借鉴混合图的欧拉回路思想这点很妙。

另:方法三还不是很理解,有机会再看看。

代码如下:(采用方法二)

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int MAXN = 2e3 + 10;
const int MAXM = 1e5 + 10;
const int INF = 0x3f3f3f3f;

struct edge {
int to, cap, next;
edge( int to = 0, int cap = 0, int next = 0 ) : to(to), cap(cap), next(next) {}
} G[MAXM];
vector<P> E;
int n, m;
int tot, head[MAXN << 1], cur[MAXN << 1];
int d[MAXN << 1];

bool bfs(int s, int t)
{

memset(d, -1, sizeof(d));
queue<int> que;
que.push(s);
d[s] = 0;

while( !que.empty() )
{
int u = que.front(); que.pop();
for( int i = head[u]; ~i; i = G[i].next )
{
edge &e = G[i];
if( e.cap > 0 && d[e.to] == -1 )
{
d[e.to] = d[u] + 1;
que.push(e.to);
}
}
}
return ~d[t];
}
int dfs(int u, int t, int f)
{

if( u == t ) return f;
int res = 0;

for( int &i = cur[u]; ~i; i = G[i].next )
{
edge &e = G[i];
if( e.cap > 0 && d[e.to] == d[u] + 1 )
{
int temp = dfs(e.to, t, min(e.cap, f));
if( temp > 0 )
{
res += temp;
f -= temp;
G[i].cap -= temp;
G[i ^ 1].cap += temp;
if( !f ) break;
}
}
}
return res;
}
int Dinic(int s, int t)
{

int f = 0;
while( bfs(s, t) )
{
memcpy(cur, head, sizeof(head));
f += dfs(s, t, INF);
}
return f;
}
void add_edge(int u, int v, int cap)
{

G[tot] = edge(v, cap, head[u]);
head[u] = tot++;
G[tot] = edge(u, 0, head[v]);
head[v] = tot++;
}
void init()
{

tot = 0;
memset(head, -1, sizeof(head));
}
int main()
{

int T;
scanf("%d", &T);
while( T-- )
{
E.clear();
init();
scanf("%d %d", &n, &m);
if( !m )
{
puts("0");
continue;
}
int s = 0, t = n + m + 1;
int u, v;
for( int i = 0; i < m; ++ i )
{
scanf("%d %d", &u, &v);
E.push_back(make_pair(u, v));
}
int l = 1, r = m;
while( r - l >= 0 )
{
int mm = (l + r) >> 1;
init();
for( int i = 1; i <= n; ++ i ) add_edge(s, i, mm);
for( int i = 0; i < m; ++ i )
{
P p = E[i];
add_edge(p.first, n + i + 1, 1);
add_edge(p.second, n + i + 1, 1);
add_edge(n + i + 1, t, 1);
}
int flow = Dinic(s, t);
if( flow == m ) r = mm - 1;
else l = mm + 1;
}
printf("%d\n", l);
}

return 0;
}
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!