CF858F Wizard's Tour 解题报告

题目描述

给定一张 \(n\) 个点 \(m\) 条边的无向图，每条边连接两个顶点，保证无重边自环，不保证连通。

你想在这张图上进行若干次旅游，每次旅游可以任选一个点 \(x\) 作为起点，再走到一个与 \(x\) 直接有边相连的点 \(y\)，再走到一个与 \(y\) 直接有边相连的点 \(z\) 并结束本次旅游。

作为一个旅游爱好者，你不希望经过任意一条边超过一次，注意一条边不能即正向走一次又反向走一次，注意点可以经过多次，在满足此条件下，你希望进行尽可能多次的旅游，请计算出最多能进行的旅游次数并输出任意一种方案。

输入输出格式

输入格式

第 \(1\) 行两个正整数 \(n\) 与 \(m\)，表示全图的点数与边数

下接 \(m\) 行，每行两个数字 \(u\) 与 \(v\) 表示一条边

输出格式

第 \(1\) 行一个整数 \(cnt\) 表示答案

下接 \(cnt\) 行，每行三个数字 \(x, y\) 与 \(z\)，表示一次旅游的路线

如有多种旅行方案，任意输出一种即可

说明

对于前 \(20\%\) 的数据， \(n \le10, m \le 20\).

对于另 \(20\%\) 的数据， \(m = n - 1\)，并且图连通

对于另 \(10\%\) 的数据，每个点的度数不超过 \(2\)

对于 \(100\%\) 的数据， \(n \le 100000, m \le 200000\)

可能还是没怎么做过构造题目吧，我打的树的特殊数据分其实改一改就是正解了。

通过手玩我们发现对一个有\(m\)条边的连通块来说，方案数量一定可以构造到\(\lfloor\frac{m}{2}\rfloor\)个。

构造方法如下

对某个连通块随便选择一个点构造一颗搜索树，在回溯的时候配对可以连接的边，如果不能两两配对，那么用上自己头上的边。

考虑为什么这样是对的，思路很简单。我们发现除了选定根的某个儿子边，所有的边都可以用上，不会产生浪费。

Code:

#include <cstdio>

#include <vector>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define Rep(i,a,b) for(int i=a;i<b;i++)

#define ed() for(int i=head[now];i;i=Next[i])

#define pb(a) push_back(a)

const int N=2e5+10;

int head[N],to[N<<1],Next[N<<1],cnt=1;

void add(int u,int v)

{

    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

int used[N<<1],ans[N<<2],n,m,tot,vis[N];

void dfs(int now,int fa,int edg)

{

    vis[now]=1;

    std::vector <int> ch;

    ed()

    {

        int v=to[i];

        if(v!=fa&&!vis[v]) dfs(v,now,i);

    }

    ed()

    {

        int v=to[i];

        if(v!=fa&&!used[i])

        {

            ch.pb(i);

            used[i^1]=1;

        }

    }

    Rep(i,0,ch.size())

    {

        if(i&1) ans[++tot]=now;

        ans[++tot]=to[ch[i]];

    }

    if(ch.size()&1)

    {

        if(fa) ans[++tot]=now,ans[++tot]=fa,used[edg]=1;

        else tot--;

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    int u,v;

    rep(i,1,m) scanf("%d%d",&u,&v),add(u,v),add(v,u);

    rep(i,1,n) if(!vis[i]) dfs(i,0,0);

    printf("%d\n",tot/3);

    rep(i,1,tot)

    {

        printf("%d ",ans[i]);

        if(i%3==0) printf("\n");

    }

    return 0;

}

2018.10.25

巴特西

CF858F Wizard's Tour 解题报告

题目描述

输入输出格式

输入格式

输出格式

说明

最新文章

热门文章