柳州企业网站建设价格,公司网站建设和推广,租一个网站服务器多少钱,wordpress 短信登录密码【题目链接】
ybt 1375#xff1a;骑马修栅栏(fence) 洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences
【题目考点】
1. 图论#xff1a;欧拉回路
欧拉回路存在的条件#xff1a;图中所有顶点的度都是偶数欧拉路径存在的条件#xff1a;图中只有两个度为奇数的顶点…【题目链接】
ybt 1375骑马修栅栏(fence) 洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences
【题目考点】
1. 图论欧拉回路
欧拉回路存在的条件图中所有顶点的度都是偶数欧拉路径存在的条件图中只有两个度为奇数的顶点。而且这两个顶点是欧拉路径的起点与终点。
求解欧拉回路使用Hierholzer算法 复杂度O(VE)O(VE)O(VE)
【解题思路】
该图是无向图顶点就是图中的顶点栅栏是边。 “栅栏都是连通的”意味着这是一个无向连通图。 “使每个栅栏都恰好被经过一次”就是每条边都经过一次。该问题为求欧拉路径。可以使用Hierholzer算法解决。 “两顶点间可能有多个栅栏”意味着可能有重边但Hierholzer算法可以处理有重边或自环的图。 “输出500进制表示法中最小的一个”即为输出字典序最小的欧拉路径顶点序列。 只需要在实现Hierholzer算法时包括选择起始顶点或某顶点的邻接点时尽量选择编号较小的顶点来访问即可。
在输入边时统计顶点编号的最大值作为总顶点数量。
首先从小到大遍历所有顶点
如果存在奇数度的顶点选择该顶点作为起始点。如果不存在奇数度的顶点那么所有顶点的度都是偶数任选顶点作为起始点。这里选择1号顶点为起始点。
从起始顶点出发进行深搜使用Hierholzer算法求欧拉路径。为了满足条件必须按顶点编号从小到大访问一个顶点的所有邻接点。
可以使用邻接矩阵或邻接表完成该题。
【题解代码】
解法1邻接矩阵
#includebits/stdc.h
using namespace std;
#define N 505
int edge[N][N], n, m, deg[N];//n:顶点数 m:边数 deg[i]:顶点i的度
stackint stk;
void dfs(int u)//Hierholzer算法
{for(int v 1; v n; v){if(edge[u][v]){edge[u][v]--;edge[v][u]--;dfs(v);}}stk.push(u);
}
int main()
{int f, t, st 1;//st:起点 cin m;for(int i 1; i m; i){cin f t;n max(n, max(f, t));edge[f][t];edge[t][f];deg[f];deg[t];}for(int v 1; v n; v)//如果找到奇数度顶点就从奇数度顶点出发否则从1出发 {if(deg[v] % 2 1){st v;break;}}dfs(st);while(stk.empty() false){cout stk.top() endl;stk.pop();}return 0;
}解法2邻接表
#includebits/stdc.h
using namespace std;
#define N 505
#define M 1050
struct Node
{int v, e;//v顶点 e边编号 Node(){}Node(int a, int b):v(a), e(b){}
};
int n, m, beg[N], deg[N];//n:顶点数 m:边数 deg[i]:顶点i的度 beg[i]:顶点i的邻接点从edge[i][beg[i]]开始
bool vis[M];//vis[i]边i是否已访问过
vectorNode g[N];
stackint stk;
bool cmp(Node a, Node b)
{return a.v b.v;
}
void dfs(int u)//Hierholzer算法
{for(int i beg[u]; i g[u].size(); i){int v g[u][i].v, e g[u][i].e;if(vis[e] false){vis[e] true;dfs(v);}}stk.push(u);
}
int main()
{int f, t, st 1;//st:起点 cin m;for(int i 1; i m; i){cin f t;n max(n, max(f, t));g[f].push_back(Node(t, i));g[t].push_back(Node(f, i));deg[f];deg[t];}for(int v 1; v n; v)sort(g[v].begin(), g[v].end(), cmp);for(int v 1; v n; v){//如果找到奇数度顶点就从奇数度顶点出发否则从1出发 if(deg[v] % 2 1){st v;break;}}dfs(st);while(stk.empty() false){cout stk.top() endl;stk.pop();}return 0;
}
