P
r
o
b
l
e
m
\mathrm{Problem}
Problem
S
o
l
u
t
i
o
n
\mathrm{Solution}
Solution
显然，仙人掌不存在复杂环，这是这道题解题的关键。
对于割边，我们可以直接删。删一条边，贡献为1.对于简单环，若删
k
k
k条边，贡献是
k
−
1
k-1
k−1.
我们需要判出所有的简单环，但是我们需要解决的难题是：
形如8字型的环要判成两个。需要具体求出每一个环的大小。
此时无向图的tarjan算法、割边、并查集都不可以，我们可以尝试DFS。
我们记录图上某一个点在搜索树上的深度，若找到已经访问过的点，深度之差就是环的大小，记得需要特判环的大小大于2，因为不存在2元环（如题，没有重边）。
代码如下：
void dfs(int x
,int fa
)
{
for (int i
=Link
[x
];i
;i
=e
[i
].next
)
{
int y
= e
[i
].y
;
if (y
== fa
) continue;
if (!dis
[y
]) {
dis
[y
] = dis
[x
] + 1;
dfs(y
,x
);
}
else if (dis
[y
] < dis
[x
] + 1)
scc
[++cnt
] = dis
[x
]-dis
[y
]+1;
}
return;
}
然后就随随便便排个序贪心乱搞一下就A拉~
\mathrm{Code}
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
const int N
= 1e6 + 10;
const int M
= 2e6 + 10;
int n
, m
, k
, tot(0), cnt(0), ans(0);
int dis
[N
], scc
[N
], Link
[N
];
struct node
{
int y
, next
;
} e
[M
* 2];
int read(void)
{
int s
= 0, w
= 0; char c
= getchar();
while (c
< '0' || c
> '9') w
|= c
== '-', c
= getchar();
while (c
>= '0' && c
<= '9') s
= s
*10+c
-48, c
= getchar();
return w
? -s
: s
;
}
void add(int x
,int y
) {
e
[++tot
] = node
{y
,Link
[x
]};
Link
[x
] = tot
;
}
void dfs(int x
,int fa
)
{
for (int i
=Link
[x
];i
;i
=e
[i
].next
)
{
int y
= e
[i
].y
;
if (y
== fa
) continue;
if (!dis
[y
]) {
dis
[y
] = dis
[x
] + 1;
dfs(y
,x
);
}
else if (dis
[y
] < dis
[x
] + 1)
scc
[++cnt
] = dis
[x
]-dis
[y
]+1;
}
return;
}
int main(void)
{
n
= read(), m
= read(), k
= read();
for (int i
=1,x
,y
;i
<=m
;++i
)
{
x
= read(), y
= read();
add(x
,y
), add(y
,x
);
}
for (int i
=1;i
<=n
;++i
)
{
if (dis
[i
] > 0) continue;
dis
[i
] = 1;
dfs(i
,0);
ans
++;
}
int edge
= m
;
for (int i
=1;i
<=cnt
;++i
)
edge
-= scc
[i
];
if (edge
>= k
) {
ans
+= k
;
std
::cout
<<ans
;
return 0;
}
ans
+= edge
, k
-= edge
;
std
::sort(scc
+1,scc
+cnt
+1);
std
::reverse(scc
+1,scc
+cnt
+1);
for (int i
=1;i
<=cnt
;++i
)
{
if (k
- scc
[i
] >= 0) {
k
-= scc
[i
];
ans
+= scc
[i
] - 1;
}
else {
ans
+= k
-1;
break;
}
}
std
::cout
<<ans
;
return 0;
}
