洛谷P2731题解

传送锚点

摸鱼环节

[USACO3.3] 骑马修栅栏 Riding the Fences

题目背景

Farmer John 每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。

题目描述

John 是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。

John 的农场上一共有 \(m\) 个栅栏，每一个栅栏连接两个顶点，顶点用 \(1\) 到 \(500\) 标号（虽然有的农场并没有那么多个顶点）。一个顶点上至少连接 \(1\) 个栅栏，没有上限。两顶点间可能有多个栅栏。所有栅栏都是连通的（也就是你可以从任意一个栅栏到达另外的所有栅栏）。John 能从任何一个顶点（即两个栅栏的交点）开始骑马，在任意一个顶点结束。

你需要求出输出骑马的路径（用路上依次经过的顶点号码表示)，使每个栅栏都恰好被经过一次。如果存在多组可行的解，按照如下方式进行输出：如果把输出的路径看成是一个 \(500\) 进制的数，那么当存在多组解的情况下，输出 \(500\) 进制表示法中最小的一个 （也就是输出第一位较小的，如果还有多组解，输出第二位较小的，以此类推）。

输入数据保证至少有一个解。

输入格式

第一行一个整数 \(m\)，表示栅栏的数目。

从第二行到第 \((m+1)\) 行，每行两个整数 \(u,v\)，表示有一条栅栏连接 \(u,v\) 两个点。

输出格式

共 \((m+1)\) 行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。

数据保证至少有一组可行解。

样例 #1

样例输入 #1

9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6

样例输出 #1

1
2
3
4
2
5
4
6
5
7

提示

对于 \(100\%\) 的数据，\(1 \leq m \leq 1024,1 \leq u,v \leq 500\)。

题目翻译来自NOCOW。

USACO Training Section 3.3

这一把熟人局，老将Farmer john申请出战还是日常帮助Farmer john处理休闲问题。今日份的john也是闲的蛋疼骑上了马。不出意外的话就要出题，他居然还想修栅栏，直接干出一道欧拉路径。

正片开始

1. 我们选择用vector存个图，并将每个点所连接的点按照大小排序，以此处理输出顺序。

code：

for(int i=1;i<=m;i++)
{
    int u,v;cin>>u>>v;
    g[u].push_back(v);g[v].push_back(u);
    b[u][v]++,b[v][u]++;n=max(n,max(u,v));
}
for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());

2. 开始搞点，不断遍历每个点的临界点，在\(a\)到\(b\)有边的情况下进行递归处理，并将边删除以免重复计算。

code：

void findx(int x)
{
    for(int i=0;i<g[x].size();i++)
    {
        if(b[x][g[x][i]]>0)
        {
            b[x][g[x][i]]--,b[g[x][i]][x]--;
            findx(g[x][i]);
        }
    }
    ans[++l]=x;
}

3. 特判不是欧拉回路的情况，即存在\(g[i].size()\)为奇数。

code：

for(int i=1;i<=n;i++)
{
    if(g[i].size()%2)
    {
        findx(i);f=1;
        break;
    }
}
if(f==0)
{
    for(int i=1;i<=n;i++)
    {
        if(g[i].size())
        {
            findx(i);
            break;
        }
    }
}
for(int i=l;i>=1;i--) cout<<ans[i]<<endl;

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int m,b[N][N],ans[N],l=0,n=0,f=0;
vector<int>g[N];
void findx(int x)
{
    for(int i=0;i<g[x].size();i++)
    {
        if(b[x][g[x][i]]>0)
        {
            b[x][g[x][i]]--,b[g[x][i]][x]--;
            findx(g[x][i]);
        }
    }
    ans[++l]=x;
}
int main()
{
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v);g[v].push_back(u);
        b[u][v]++,b[v][u]++;n=max(n,max(u,v));
    }
    for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
    for(int i=1;i<=n;i++)
    {
        if(g[i].size()%2)
        {
            findx(i);f=1;
            break;
        }
    }
    if(f==0)
    {
        for(int i=1;i<=n;i++)
        {
            if(g[i].size())
            {
                findx(i);
                break;
            }
        }
    }
    for(int i=l;i>=1;i--) cout<<ans[i]<<endl;
    return 0;
}

完结收工！！！！！

个人主页

看完点赞，养成习惯

\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)