Codeforces Round #434 Div.1 D graph

66 阅读 0 评论 44 点赞

我是靠谱客的博主开心魔镜，最近开发中收集的这篇文章主要介绍Codeforces Round #434 Div.1 D graph，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

给定一张n个点m条边的无向图，每条边连接两个顶点，保证无重边自环，不保证连通
你想在这张图上进行若干次旅游，每次旅游可以任选一个点x作为起点，再走到一个与x 直接有边相连的点y，再走到一个与y 直接有边相连的点z 并结束本次旅游
作为一个旅游爱好者，你不希望经过任意一条边超过一次，注意一条边不能即正向走一次又反向走一次，注意点可以经过多次，在满足此条件下，你希望进行尽可能多次的旅游，请计算出最多能进行的旅游次数并输出任意一种方案

Input

第1 行两个正整数n 与m，表示全图的点数与边数
下接m 行，每行两个数字u 与v 表示一条边

Output

第1 行一个整数cnt 表示答案
下接cnt 行，每行三个数字x, y 与z，表示一次旅游的路线
如有多种旅行方案，任意输出一种即可

Data Constraint

对于前20% 的数据，n <= 10;m <= 20.
对于令20% 的数据，m = n - 1，并且图连通
对于令10% 的数据，每个点的度数不超过2
对于100% 的数据，n <= 100000;m <= 200000

题解

题目的意思就是两条边，使得它们之间有公共点。
考虑一种贪心做法。
每次将一个点x，将它连出去的边进行两两匹配。

对于x枚举的顺序，就先将图看成树。

code

#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#define ll long long
#define N 200003
#define db double
#define P putchar
#define G getchar
#define mo 998244353
using namespace std;
char ch;
void read(int &n)
{
    n=0;
    ch=G();
    while((ch<'0' || ch>'9') && ch!='-')ch=G();
    ll w=1;
    if(ch=='-')w=-1,ch=G();
    while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
    n*=w;
}

db max(db a,db b){return a>b?a:b;}
db min(db a,db b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}

int n,m,x,y,ans,w[N][3];
bool bz[N],p[N*2];
int nxt[N*2],to[N*2],b[N],tot;
int d[N],q[N],f[N];

void ins(int x,int y)
{
    nxt[++tot]=b[x];
    to[tot]=y;
    b[x]=tot;
}

void bfs(int x)
{
    int head=0,tail=1;bz[d[1]=x]=0;
    while(head<tail)
    {
        int y=d[++head];
        for(int i=b[y];i;i=nxt[i])
            if(bz[to[i]])bz[to[i]]=0,d[++tail]=to[i],f[to[i]]=y;
    }
    q[0]=0;
    for(int i=tail;i;i--)
    {
        int y=d[i];q[0]=0;

        for(int j=b[y];j;j=nxt[j])
            if(p[j] && to[j]!=f[y])q[++q[0]]=j;
        for(int j=b[y];j;j=nxt[j])
            if(p[j] && to[j]==f[y])q[++q[0]]=j;

        for(int j=1;j+1<=q[0];j=j+2)
        {
            p[q[j]]=p[q[j]^1]=0;
            p[q[j+1]]=p[q[j+1]^1]=0;
            w[++ans][0]=to[q[j]];
            w[ans][1]=y;
            w[ans][2]=to[q[j+1]];
        } 
    }
}

int main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    read(n);read(m);tot=1;
    for(int i=1;i<=m;i++)
        read(x),read(y),ins(x,y),ins(y,x);
    memset(bz,1,sizeof(bz));
    memset(p,1,sizeof(p));

    for(int i=1;i<=n;i++)
        if(bz[i])bfs(i);

    write(ans),P('n');
    for(int i=1;i<=ans;i++)
        write(w[i][0]),P(' '),write(w[i][1]),P(' '),write(w[i][2]),P('n');
}