Fork me on GitHub

Codeforces858F

Codeforces858F题解:

题意:

  • 给你一张$n$点$m$边无向图,询问最多进行几次操作,每次操作删去两条相邻的边,并给出方案。

题解:

  • 题解还是蛮神的,直接证明一个连通块的答案可以达到上界,直接给了构造,应该挺显然的。大概就是通过搜索树尽量先匹配深度较低的点向下连得边就好了。

代码:

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
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 200009
using namespace std;
int n,m,first[N],number=1,vis[N],used[N<<1],ans,fa[N],deep[N];
struct edge
{
int to,next;
void add(int x,int y)
{
to=y,next=first[x],first[x]=number;
}
}e[N<<1];
struct node
{
int x,y,z;
node(int x=0,int y=0,int z=0):x(x),y(y),z(z){}
}Ans[N];
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return x*s;
}
void dfs(int x,int last)
{
deep[x]=deep[fa[x]]+1;
vis[x]=1;
int num=0;
for (int i=first[x];i;i=e[i].next)
if (!vis[e[i].to]) fa[e[i].to]=x,dfs(e[i].to,i);
bool flag=1;
for (int i=first[x];i;i=e[i].next)
if (deep[e[i].to]>deep[x]&&!used[i])
{
if (flag) Ans[++ans].x=e[i].to,Ans[ans].y=x;
else Ans[ans].z=e[i].to;
flag^=1;
used[i]=used[i^1]=1;
}
if (!flag)
{
Ans[ans].z=fa[x];
if (fa[x]==0) ans--;
used[last]=used[last^1]=1;
}
}
int main()
{
n=read(),m=read();
for (int i=1;i<=m;i++)
{
int x=read(),y=read();
e[++number].add(x,y),e[++number].add(y,x);
}
for (int i=1;i<=n;i++)
if (!vis[i]) dfs(i,0);
printf("%d\n",ans);
for (int i=1;i<=ans;i++)
printf("%d %d %d\n",Ans[i].x,Ans[i].y,Ans[i].z);
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces858F

文章作者:wzf2000

发布时间:2017年12月26日 - 12:12

最后更新:2017年12月26日 - 12:12

原始链接:https://wzf2000.github.io/2017/12/26/Codeforces858F/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。