网站建设费用怎么做分录,做校园网站代码,室内装修设计企业,企业宣传片脚本最近学了一波国家集训队2018论文的最后一个专题。顺便带上了一些我的注解。 先放一波这个论文
1.基本概念
欧拉图问题是图论中的一类特殊的问题。在本文的介绍过程中#xff0c;我们将会使用一些图 论术语。为了使本文叙述准确#xff0c;本节将给出一些术语的定义。
定义…最近学了一波国家集训队2018论文的最后一个专题。顺便带上了一些我的注解。 先放一波这个论文
1.基本概念
欧拉图问题是图论中的一类特殊的问题。在本文的介绍过程中我们将会使用一些图 论术语。为了使本文叙述准确本节将给出一些术语的定义。
定义 1.1. 图 G 中与顶点 v 关联的边数自环统计两次称为图 G 中顶点 v 的度。特别地 对于有向图 G 进入顶点 v 的边的条数称为顶点 v 的入度从顶点v 引出的边的条数称为 顶点 v 的出度。
定义 1.2. 图 G 中度为奇数的点称为奇顶点度为偶数的点称为偶顶点度为 0 的点称为孤 立点。
定义 1.3. 对于无向图 G 中的两点 u 和 v 若存在 u 到 v 的路径则称 u 和 v 是连通的。如 果图 G 中任意两点都是连通的则称图 G 为连通图。对于有向图 G 将所有的有向边替 换为无向边得到图 G 的基图若图 G 的基图是连通的则称图 G 是弱连通图。
定义 1.4. 对于图 G 中边 e 若删去 e 后图 G 的连通分量的数量增加则称边 e 为 G 的桥。 意思是将桥删掉以后会让这个图分裂成两个图。
定义 1.5. 图 G 中一条路径指一个顶点与边的交替序列。回路指满足 v0 vm 的一条路径一般不区分起点。
定义 1.6. 图 G 中经过每条边恰一次的回路称为欧拉回路经过每条边恰一次的路径称为欧拉路径。
定义 1.7. 存在欧拉回路的图称为欧拉图存在欧拉路径但不存在欧拉回路的图称为半欧拉 图。
定义 1.8. 不含平行边也称重边也不含自环的图称为简单图。
2.欧拉图的判定
注:我并没有照抄论文上的证明而是按照自己的理解写的可能并不严谨意会即可。
2.1无向欧拉图
定理 2.1. 无孤立点的无向图 G 为欧拉图当且仅当图 G 连通且所有顶点的度都是偶数。 证明 设一个点的度数是2k 那么对于非起点就会有k次进入和k次出去第一次是进入所以最后一次操作一定是出去。 对于起点也会有k次进入和k次出去第一次是出去所以最后一次操作一定是进入这个点即可形成欧拉回路。
定理 2.2. 如果无向连通图有 2k 个奇顶点则图 G 可以用 k 条路径将图 G 的每一条边经过一次且至少要使用 k 条路径。 证明 我们可以将2k个奇顶点两两分组一共就是k组。那么这样就可以有k条欧拉路径了。 特别地如果是2k1个奇顶点那么至少要k1条路径。也就是用上面的k条路径在加上另外一条一共k1。
2.2 有向欧拉图
其实有向欧拉图和无向欧拉图的结论类似证明过程基本相同因此略过证明过程请读者自己思考很好想。
定理 2.4. 无孤立点的有向图 G 为欧拉图当且仅当图 G 弱连通且所有顶点的入度等于出度。
定理 2.5. 对于连通有向图所有顶点入度与出度差的绝对值之和为 2k 则图 G 可以用 k条路径将图 G 的每一条边经过一次且至少要使用 k 条路径。
定理 2.6. 无孤立点的有向图 G 为半欧拉图当且仅当图 G 弱连通且恰有一个顶点 u 入度比出度小 1 一个顶点 v 入度比出度大 1 其余顶点入度等于出度。此时存在 u 作为起点 v 作为终点的欧拉路径。
3.欧拉回路的生成
第2章的定理一定要好好的掌握我们接下来将会经常用到。 既然我们已经学会了判定欧拉图本章介绍的是如何在一个欧拉图中找到欧拉回路或者欧拉路径。
那么我们先引入一个问题。
问题 3.1. 给定无向欧拉图 G (V, E) 求出图 G 的一条欧拉回路。 解决这类问题有两种方法Fluery算法与Hierholzer。 由于前者在在做题和比赛中基本不会用到所以本节中我们将介绍Hierholzer算法来解决此问题。
hierholzer算法
3.2.1 算法简介
该算法也被称作“套圈算法”或“DFS法”。因为效率高、代码短等优势该算法成为信息竞赛中最常用的欧拉路径算法。
该算法的思路与定理2.1的构造思路基本相同。任选一起点沿任意未访问的边走到相邻节点直至无路可走。此时必然回到起点形成了一个回路此时图中仍有部分边未被访问。
在退栈的时候找到仍有未访问边的点从该点为起点求出另一个回路将该回路与之前求出的回路拼接。如此反复直至所有的边都被访问。
3.2.2 算法流程
任取 G 中的一个顶点 v0将 v0 加入栈S。记栈 S 顶端元素为 u 若 u 不存在未访问的出边将 u 从栈 S 中弹出并将 u 插入路径 P 的前端。否则任选一条未访问的出边 (u, v) 将 v 加入栈 S 。重复(2)直到栈 S 为空此时 P 为所求得的欧拉回路。 图3(a)-(d)展现了Hierholzer算法的执行过程不同颜色表示在执行过程中找到的不同回路。图3(e)表示在这个例子上Hierholzer算法得到的最终结果
3.2.3程序的实现
伪代码 代码
int size,path[M];
void Solve(int u){ for(int ilast[u];i;ilast[u]){int ve[i].v;last[u]e[i].nxt;Solve(v);}path[size]id;
}我们可以使用链表维护边无向边用两条反向的有向边表示删除时同时删去两条边。 Hierholzer算法的时间复杂度为 O(m) 。这个算法也可以很容易地按照算法流程中描述的方式改成非递归形式。
我也想到了一个比较合理的证明 对于无向图因为存在欧拉回路所以每个点的度数都是偶数。也就是说假设一开始就从一个点出去最后一定会回到这个点同理如果一开始从这个点进来那么最后也一定会出去。 所以我们开始从1一直走那么一定会回到1。然后我们再回溯的过程中看哪个点还有边没有访问过的就假设这个点是起点然后搜一次因为度数是偶数所以最后一定会回到这个点那么我们就把这个点得到的回路插到栈里面就这样一直反复最后得到结果。
3.2.4 算法分析与扩展
该算法同样可以解决有向图的情况与求解欧拉路径
问题 3.3. 给定有向欧拉图 G (V, E) 求出图 G 的一条欧拉回路。
解法. 对于有向图只需用链表维护有向边即可删除时只需删除一条边。
问题 3.4. 给定无向或有向半欧拉图 G (V, E) 求出图 G 的一条欧拉路径。
解法. 对于包含两个奇顶点的无向图以任意一个奇顶点作为起点。对于有向图找到入度比出度小 1 的顶点作为起点。使用上述算法就可以得到一条欧拉路径。此时算法的执行过程就是将一条路径与多个回路依次合并。
我们还可以使用该算法求解对字典序有要求的问题
问题 3.5. 给定无向或有向欧拉图或半欧拉图 G (V, E) 求出图 G 的一条字典序最小的欧拉回路路径。
解法. 我们对每个点 u 关联的出边 (u, v) 按照 v 排序找到图中编号最小的可作为起点的点出发每一次走到编号最小的相邻节点 v 。在算法执行过程中先会找到包含起点的一个字典序最小的回路或路径。从后向前找到一个仍有未访问边的节点将一个包含该点的字典序最小的回路拼接到已求得的回路或路径中。如此反复就能得到字典序最小的回 路或路径。
问题 3.6. 给定无向或有向连通图 G (V, E) 求出最少的路径将图 G 的每一条边经过一次。
解法. 这一问题在定理2.2中已经给出了构造方案对奇点两两配对在每对点之间加入一条边构成欧拉图。求出新图的欧拉回路将回路从新加入的边处断开就得到了 k 条路径。
例题 caioj1229 【题目】 给出n个点编号1~nm条边有人从1点出发请输出每条边只经过一次的边的编号。如有多组解输出编号字典序最小的路径 【输入】 第一行输入两个个整数n(2n500),m(1m100000) 接下来m1行每行输入两个整数x,y表示有一条从x去到y的单向边 【输出】 输出一条路径上边的编号每个边的编号都以空格隔开行末不输出空格。 若不存在输出‘NO’ 【样例输入】 5 5 1 2 2 3 3 4 4 5 5 1 【样例输出】 1 2 3 4 5 【样例解析】 人从1-2-3-4-5-1形成了一条路径路径中经过了所有的边。 所以边的编号就是1-2-3-4-5
先要判断是否是欧拉路径。如果是用邻链表就反着建边然后跑一遍Hierholzer即可。 注意如果用dfs的做法的话在本机评测时要手动扩栈以免出现爆栈的现象但在大部分oj和比赛都不用。具体做法如下打开c点击“工具”点击“编译选项”找到“编译器”在“编译时加上以下命令”那一栏里面加入指令“-Wl,--stack134217728”。就可以了以下内容亦是如此。 1342177282^27方便记忆。 参考代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define il inline
#define gc getchar()
#define dg isdigit
using namespace std;
templatetypename Til void read(T x){x0;int f0;char sgc;while(!dg(s))f|s-,sgc;while( dg(s))xx*10s-48,sgc;xf?-x:x;
}
const int N5e210,M1e510;
struct edge{int v,nxt,id;
}e[M];int tot,last[N];
il void Addedge(int u,int v,int id){e[tot](edge){v,last[u],id};last[u]tot;
}
struct bian{int x,y;}b[M];
int n,m,into[N],out[N],fa[N];
int findfa(int x){return xfa[x]?x:fa[x]findfa(fa[x]);}
il void Prepare(){read(n),read(m);for(int i1;in;i)fa[i]i;for(int i1;im;i){read(b[i].x),read(b[i].y);into[b[i].y],out[b[i].x];int fxfindfa(b[i].x),fyfindfa(b[i].y);if(fx!fy)fa[fx]fy;}
}
int S,T;
il void Shut(){puts(NO);exit(0);}
il void Check(){for(int s0,i1;in;i){if(fa[i]i(into[i]||out[i]))s;if(s1)Shut();if(into[i]!out[i]){if(abs(into[i]-out[i])!1)Shut();if(into[i]-out[i]1){if(!T)Ti;else Shut();}if(out[i]-into[i]1){if(i!1)Shut();if(!S)Si;else Shut();}}}if((S!T)||(!ST))Shut();
}
il void Build(){tot0,memset(last,0,sizeof(last));for(int im;i1;i--)Addedge(b[i].x,b[i].y,i);
}
int size,path[M];
void Solve(int u,int id){for(int ilast[u];i;ilast[u]){int ve[i].v;last[u]e[i].nxt;Solve(v,e[i].id);}path[size]id;
}
void Print(){size--;for(int isize;i2;i--)printf(%d ,path[i]);printf(%d\n,path[1]);
}
int main(){Prepare();Check();Build();Solve(1,0);Print();return 0;
}4.欧拉图相关的性质
通过2、3两节的介绍我们对欧拉图的判定方法和欧拉回路的生成有了一定了解。下面我们通过解决一些实际问题分析欧拉图的相关性质。
定理 4.1. 对于任意无向连通图 G 一定存在回路使得每条边经过恰好两次。进一步地存在回路使得每条边的两个方向各经过一次。
证明 我们将图 G 的每一条边重复两次得到无向图 G1 。 G1 是连通图且所有点的度都 是图 G 中对应点的度的两倍。因此 G1 是欧拉图存在欧拉回路。 同理若把图 G 的每条无向边变为两条反向的有向边得到有向图 G2 。 G2 也存在欧 拉回路满足图 G 每条边的两个方向各经过一次。
例题 4.1. caioj 1758 【题目描述】 给定 n 个点 m 条边的无向连通图。其中 m − 2 条边经过两次余下的两条边各经过一次经过次数为一次的两条边不同就认为是不同的路径问有多少种不同的路径。 【输入格式】 第1行输入两个整数n,m 第2至第m1行每行输入两个整数u,v表示第i条边 【输出格式】 输出一个整数表示不同路径的总数 【样例输入】 4 7 1 1 1 1 3 3 1 2 2 3 4 1 4 3 【样例输出】 19
解法 将图 G 中所有的边重复两次得到图 G’ 。现在需要从 G’ 中删去两条不同的边使其存在欧拉路径满足奇顶点个数为 0 或 2 。满足条件的只有以下三种组合方式 1删去的两条边都是自环。 2删去的两条边中恰有一条为自环。 3删去的两条边均不是自环但有公共点。分别计算方案即可求出答案。时间复杂度为 O(n m) 。 由于证明过于简单所以请读者自己思考。
参考代码
#pragma GCC optimize(Ofast)
#includecstdio
#includecstring
#includealgorithm
#includeiostream
#define il inline
#define dg isdigit
#define gc getchar()
using namespace std;
typedef long long LL;
templatetypename Til void read(T x){x0;int f0;char sgc;while(!dg(s))f|s-,sgc;while( dg(s))xx*10s-48,sgc;xf?-x:x;
}
const int N1e610;
int deg[N],n,m;
struct bian{int x,y;
}a[N];int tot,ring;
int Rsort[N],sa[N],y[N];
LL ans0;
int main(){read(n),read(m);totring0;int u,v;for(int i1;im;i){read(u),read(v);if(uv)ring;else{if(uv)swap(u,v);a[tot](bian){u,v};deg[u],deg[v];}}memset(Rsort,0,sizeof(Rsort));for(int i1;im;i)Rsort[a[i].y];for(int i2;in;i)Rsort[i]Rsort[i-1];for(int im;i1;i--)sa[Rsort[a[i].y]--]i;memset(Rsort,0,sizeof(Rsort));memcpy(y,sa,sizeof(sa));for(int i1;im;i)Rsort[a[i].x];for(int i2;in;i)Rsort[i]Rsort[i-1];for(int im;i1;i--)sa[Rsort[a[y[i]].x]--]y[i];ans(LL)ring*(ring-1)/2;ans(LL)ring*(m-ring);int now1;for(int i2;in;i){if(a[sa[i]].xa[sa[i-1]].xa[sa[i]].ya[sa[i-1]].y)now;else ans-(LL)now*(now-1)/2,now1;}ans-(LL)now*(now-1)/2;for(int i1;in;i)ans(LL)deg[i]*(deg[i]-1)/2;printf(%lld\n,ans);return 0;
}
定理 4.2. 对于无向图 G 所有顶点的度都是偶数等价于图 G 有圈分解。圈分解即为用若干个圈不重复经过顶点的回路使图G的每一条边恰经过一次。
证明. 这一定理我们其实在一开始介绍的定理2.1中就已经证明了只是因为章节的侧重不同没有将这一定理提出。该定理也可以描述成点度均为偶数等价于存在回路分解。该定理揭示了所有点度为偶数的等价性表述虽然看似简单但往往在解题中经常用到。
例题4.2 caioj2530 【题目描述】 给定 n 个点 m 条边的无向图边有黑白两种颜色。 现在你可以进行若干次回路反色操作每次操作从任意点出发每经过一条边将其颜色反转最后回到起点。 判断能否通过若干次操作使这张图所有边都变成白色。 若可以求出最少操作次数。否则输出can’t finish it 【输入格式】 第1行输入两个整数n,m 第2-m1行每行输入两个整数x,y表示边 【输出格式】 若可以满足要求则输出最少操作次数 否则输出can’t finish it 【输入样例1】 4 6 1 2 0 2 3 0 3 4 0 4 1 0 1 3 1 2 4 1 【输出样例1】 1 【输入样例2】 4 4 1 2 1 2 3 1 3 4 0 4 1 0 【输出样例2】 can’t finish it 【数据范围】 对于40%的数据满足1n1000,1m100000 对于100%的数据满足1n,m10^6
可以发现要想满足条件。黑边必须经过奇数次白边必须进过偶数次。否则无法满足条件。 在从贪心的角度思考一下就可以的出一下的结果。 引理 在最优的策略下会黑边都只会经过1次白边都只会经过0或2次。 证明 对于黑边设其连接的两点为u,v。假如从u进入最终必然会从v出来。既然已经从u进入了也没有必要再从v折回u走一遍因此只会进过这条黑边一次从v进入同理。 对于白边设其连接的两点为u,v我们可以选择不从这条边经过即为0次或者选择从u进入搜索与v点相连的边最终也一定会u点出来可以证明出这条边只会经过2次。 证毕。 证明是我自己写的没有照抄论文不足之处请谅解
由此得之若黑边构成的图每个点的度数均为偶数则可以达到目标否则一定不行。具体地因为白边度数为偶数也就是从哪个点进入就从哪个点出来所以白边仅能减少操作次数因此黑边必须要构成欧拉图
所以求解方法如下: 1.判断是否能完成若不能则输出“can’t finish it”并结束程序 2.求出带有黑边的联通分量并输出这个数。
参考代码
#pragma GCC optimize(Ofast)
#includecstdio
#includecstring
#includealgorithm
#includeiostream
#define il inline
#define dg isdigit
#define gc getchar()
using namespace std;
typedef long long LL;
templatetypename Til void read(T x){x0;int f0;char sgc;while(!dg(s))f|s-,sgc;while( dg(s))xx*10s-48,sgc;xf?-x:x;
}
const int N1e610;
int n,m;
struct edge{int v,nxt,color;
}e[N1];int tot,last[N];
il void Addedge(int u,int v,int color){e[tot](edge){v,last[u],color};last[u]tot;e[tot](edge){u,last[v],color};last[v]tot;
}
bool vis[N];int deg[N];
int dfs(int u){vis[u]1;int ans1;for(int ilast[u];i;ie[i].nxt){int ve[i].v;anse[i].color;if(!vis[v])ansdfs(v);}return ans;
}
int main(){read(n),read(m);for(int i1;im;i){int x,y,c;read(x),read(y),read(c);Addedge(x,y,c);if(!c)deg[x],deg[y];}bool bk1;for(int i1;in;i)if(deg[i]1){bk0;break;}if(!bk){puts(cant finish it);return 0;}int ans0;for(int i1;in;i)if(!vis[i])ans(dfs(i)^1);printf(%d\n,ans);return 0;
}定理 4.3. 对于不存在欧拉回路的图 G 若最少用 a 条路径将图 G 的每一条边经过一次若最少在图 G 中加入 b 条有向边使之成为欧拉图则 a 一定等于 b 。
证明. 我们将a条路径分出来再利用a条边将相邻两个路径收尾连起来构成一个环那么b就等于a了。
例题 4.3 caioj2531 【题目描述】 给定n个点m条边的无向图。求最少添加多少条无向边后 使得图存在从1号点出发又回到1号点的欧拉回路。 【输入格式】 第1行输入两个整数n,m 第2-m1行每行输入两个整数x,y表示边 【输出格式】 输出最少添加的边数 【输入样例1】 4 2 1 2 3 4 【输出样例1】 2 【输入样例2】 4 3 1 2 3 4 4 2 【输出样例2】 1 【数据范围】 对于40%的数据满足1n103,1m105 对于100%的数据满足1n,m10^6 【提示】 欧拉回路的定义如下 在图 G 中经过每条边不是点恰一次的回路称为欧拉回路 经过每条边恰一次的路径称为欧拉路径。
我们要结合运用定理2.5和定理4.3来求解此题。 定义ab两个整数初始化为0 对于每一个联通分量孤立点除外因为欧拉回路只是说要经过所有的边如果该联通分量全部都是偶数数点我们让b1否则a加上该连通分量中偶数点的个数。 求完以后结果就是 a / 2 b a/2b a/2b特别地图本来就是欧拉图和1是孤立点的情况要特殊讨论。
参考代码
#pragma GCC optimize(Ofast)
#includecstdio
#includecstring
#includealgorithm
#includeiostream
#define il inline
#define dg isdigit
#define gc getchar()
using namespace std;
templatetypename Til void read(T x){x0;int f0;char sgc;while(!dg(s))f|s-,sgc;while( dg(s))xx*10s-48,sgc;xf?-x:x;
}
const int N1e610;
int n,m;
struct edge{int v,nxt;
}e[N1];int tot,last[N];
il void Addedge(int u,int v){e[tot](edge){v,last[u]};last[u]tot;e[tot](edge){u,last[v]};last[v]tot;
}
int deg[N],bel[N],siz[N],odd[N];int flag;
void Dfs(int u){bel[u]flag;siz[u]1;odd[u]deg[u]1;for(int ilast[u];i;ie[i].nxt){int ve[i].v;if(bel[v])continue;Dfs(v);siz[u]siz[v];odd[u]odd[v];}
}
int main(){read(n),read(m);tot0;memset(last,0,sizeof(last));for(int i1;im;i){int u,v;read(u),read(v);Addedge(u,v);deg[u],deg[v];}for(int i1;in;i)if(!bel[i]){flagi;Dfs(i);}int ansa0,ansb0;for(int i1;in;i)if(bel[i]i(i1||siz[i]1)){if(!odd[i])ansb;else ansaodd[i];}if(!ansaansb1)puts(0);else printf(%d\n,(!ansa?0:((ansa-1)/21))ansb);return 0;}5 欧拉图的生成问题
在解决实际的应用问题时我们需要先在欧拉图性质的引导下把问题转换为图论模型。
再借助一些其他知识与算法将图论模型生成出我们所需要的欧拉图。
在本节中我们将通过几个例子介绍在欧拉图生成问题中的思路与技巧。
5.1 De Bruijn序列
问题5.1
求出一个 2 n 2^n 2n位环形 0/1 串满足所有 2 n 2^n 2n个长度为 n 的子串恰为所有 2 n 2^n 2n个的 n 位的 0/1 串。
解法
经过观察可以发现沿着这个环往下走一位那么就等于将原来的左移一位并在最后加上0或1。 设原来这个串为 x 1 x 2 . . . x n x_1x_2...x_n x1x2...xn。那么变化以后就是 x 2 x 3 . . . x n − 1 0 x_2x_3...x_{n-1}0 x2x3...xn−10或 x 2 x 3 . . x n − 1 1 x_2x_3..x_{n-1}1 x2x3..xn−11公共部分是 x 2 x 3 . . . x n − 1 x_2x_3...x_{n-1} x2x3...xn−1。 一个很容易想到的思路是将所有的0/1串看成 2 n 2^n 2n个点每个点向 x 2 x 3 . . . x n − 1 0 x_2x_3...x_{n-1}0 x2x3...xn−10和 x 2 x 3 . . x n − 1 1 x_2x_3..x_{n-1}1 x2x3..xn−11连一条有向边所以只需要每个点经过一次就能满足结果了。即哈密顿路径。然而求解这个问题是相当困难的。所以我们要尝试转化这个模型。
我们不妨将点和边所代表的意义互换。即用边表示0/1串。
那么我们用 2 n − 1 2^{n-1} 2n−1个点表示公共部分然后连接 2 n 2^n 2n条边。每条边的编号就代表了0/1串那么连的有向边的顶点就是这个0/1串的前n-1位和后n-1位组成的0/1串。建完模型以后跑一遍Hierholzer算法即可。
例题5.1 caioj2532
保险箱 【题目描述】 一个保险箱有 n 位数字密码正确输入密码后保险箱就会打开。 目前输入的最后n位数字与密码相同就算正确输入密码。 请求出一个长度为 10^nn−1字典序最小的数字序列 满足依次输入序列的每一位数字一定可以打开保险箱。 【输入格式】 仅一行输入一个整数n 【输出格式】 输出这个序列 【输入样例1】 1 【输出样例1】 0123456789 【输入样例2】 2 【输出样例2】 00102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990 【数据范围】 1n6
可以发现本题与上述的问题再本质上是一样的唯一不同点就是二进制变成了十进制。 换汤不换药我们先建立 1 0 n − 1 10^{n-1} 10n−1个点表示相同的部分然后建立 1 0 n 10^n 10n条边表示密码。 然后就跑一次欧拉路径即可。如果要使字典序最小仅需要让每个点先搜索与它相连且字典序最小的边即可。时间复杂度 O ( 1 0 n ) O(10^n) O(10n)。
参考代码
#includeiostream
using namespace std;
const int N1e610;
int n;
struct edge{int v,nxt,id;
}e[N];int tot,last[N];
inline void Addedge(int u,int v,int id){e[tot](edge){v,last[u],id};last[u]tot;
}
int fac[11],len,a[11];
void get(int now,int x,int y){len0;for(int in;i0;i--)a[i]0;while(now)a[len]now%10,now/10;for(int in;i2;i--){xx*10a[i];yy*10a[i-1];}
}
int size,path[N];
void Dfs(int u,int id){for(int ilast[u];i;ilast[u]){int ve[i].v;last[u]e[i].nxt;Dfs(v,e[i].id);}path[size]id;
}
int ans[N];
int main(){cinn;fac[0]1;for(int i1;in;i)fac[i]fac[i-1]*10;for(int ifac[n]-1;i0;i--){int u0,v0;get(i,u,v);Addedge(u,v,i);}Dfs(0,-1);size--;for(int isize;i1;i--)ans[nsize-i]path[i]%10;for(int i1,ttfac[n]n-1;itt;i)putchar(ans[i]0);
}
5.2 混合图欧拉回路
问题5.2
caioj2533 混合图欧拉回路 【题目描述】 给定包含有向边与无向边的弱连通图 G (V, E)。 判断图G是否为欧拉图。若是请求按边的编号任意输出一条欧拉回路否则输出No 【输入格式】 第1行输入三个整数n,m1,m2分别表示点、有向边、无向边的个数。 接下来m1行每行两个整数u,v表示有向边 最后m2行每行两个整数u,v表示无向边 【输出格式】 若有则第1行输出起点第二行按边的编号任意输出一条欧拉回路否则输出No。 对于边的编号我们定义有向边1m1的编号为1m1无向边1m2的编号为m11m1m2 【输入样例1】 5 4 2 2 1 3 2 4 5 3 4 1 3 5 3 【输出样例1】 1 1 5 4 3 6 2 【输入样例2】 5 4 2 1 2 3 2 4 5 3 4 1 3 5 3 【输出样例2】 No 【数据范围】 1n300,1m1,m21000
因为如果要在一个有向图中求出欧拉回路必须保证每一条边的入度等于出度。然而在这一题中有无向边。 因此我们需要确定这些无向边的方向。 设 s ( i ) s(i) s(i)表示点i出度减去入度的值若要满足条件必须使得 s ( i ) 1 i n 0 s(i)_{1in}0 s(i)1in0。我们发现加入将一条u-v的边反转成v-u那么 s ( u ) s(u) s(u)就会减小2 s ( v ) s(v) s(v)就会增加2。 想到这种匹配问题我们就可以把这个看作多源汇的最大流模型。 建图方式如下先假设无向边都是u-v。对于一个点如果 s ( u ) 0 s(u)0 s(u)0则从源点向u连一条容量为 a b s ( s ( u ) / 2 ) abs(s(u)/2) abs(s(u)/2)的边若 s ( u ) 0 s(u)0 s(u)0则从u向汇点连一条容量为 a b s ( s ( u ) / 2 ) abs(s(u)/2) abs(s(u)/2)的边。对于每条无向边按照定向的方向连边容量为1。 跑一次最大流如果不能流满则不存在合法方案。如果有哪条无向边的有流量那么就将这条边反转。 然后跑欧拉回路即可。
值得一提的是如果存在 s ( i ) 1 i n 2 k 1 s(i)_{1in}2k1 s(i)1in2k1其中k为整数那么一定不存在欧拉回路。 还有就是关于流量可以随意流不用割点这个问题的解释假设有a-b-cs(a)2,s(b)0,s©-2。那么我们可以将三条边都反转也就是a-b-cs(a)s(b)s(c )0。论文中并没有对此给予解释
参考代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includecstdlib
#includequeue
#define il inline
#define gc getchar()
#define dg isdigit
using namespace std;
templatetypename Til void read(T x){x0;int f0;char sgc;while(!dg(s))f|s-,sgc;while( dg(s))xx*10s-48,sgc;xf?-x:x;
}
const int N3e210,M1e310;
int n,m1,m2;
struct node{int y,c,nxt;
}a[(NM)1];int len,head[N],S,T;
il void ins(int x,int y,int c){len;a[len].yy;a[len].cc;a[len].nxthead[x];head[x]len;len;a[len].yx;a[len].c0;a[len].nxthead[y];head[y]len;
}
int h[N];
il bool bt_h(){memset(h,0,sizeof(h));h[S]1;queueintq;q.push(S);while(!q.empty()){int xq.front();q.pop();for(int khead[x];k;ka[k].nxt){int ya[k].y;if(a[k].c!h[y])h[y]h[x]1,q.push(y);}}return h[T];
}
int cur[N];
int dfs(int x,int f){if(xT)return f;int role0,t;for(int kcur[x];k;ka[k].nxt){int ya[k].y;if(a[k].ch[y]h[x]1){role(tdfs(y,min(a[k].c,f-role)));a[k].c-t,a[k^1].ct;if(rolef)break;}}if(!role)h[x]0;return role;
}
il int Dicnic(){int s0;while(bt_h()){memcpy(cur,head,sizeof(head));sdfs(S,1e9);}return s;
}
struct bian{int x,y;
}b[M1];int s[N];
int size,path[M1];
struct edge{int v,nxt;
}e[M1];int tot,last[N];
il void Addedge(int u,int v){e[tot](edge){v,last[u]};last[u]tot;
}
void Dfs(int u,int id){for(int ilast[u];i;ilast[u]){int ve[i].v;last[u]e[i].nxt;Dfs(v,i);}path[size]id;
}
int main(){read(n),read(m1),read(m2);for(int x,y,c,i1;im1;i){read(x),read(y);b[i](bian){x,y};s[x],s[y]--;}for(int x,y,c,i1;im2;i){read(x),read(y);b[m1i](bian){x,y};s[x],s[y]--;}int s10,s20;for(int i1;in;i){if(abs(s[i])1){puts(No);return 0;}if(s[i]0)s2s[i];else s1s[i];}if(s1s2!0){puts(No);return 0;}len1;memset(head,0,sizeof(head));Sn1,Tn2;for(int i1;in;i){if(s[i]0)ins(i,T,abs(s[i])1);else ins(S,i,s[i]1);}int poslen1;for(int im11;im1m2;i)ins(b[i].x,b[i].y,1);int ansDicnic();if(ans*2!s1){puts(No);return 0;}for(int im11;im1m2;i,pos2){if(!a[pos].c)swap(b[i].x,b[i].y);}for(int i1;im1m2;i)Addedge(b[i].x,b[i].y);Dfs(1,-1);size--;for(int isize;i1;i--)printf(%d ,path[i]);printf(%d\n,path[1]);return 0;
}
5.3 中国邮递员问题
问题 5.3. 给定有向带权连通图 G (V, E) 求出一条总边权和最小的回路使得经过每一条边至少一次。
解法. 这道题目看起来比较复杂我们可以先考虑一些简单情况。如果给定的图 G 是欧拉图显然不需要重复走任意一条边欧拉回路就是符合要求的路线。如果图G为半欧拉图存在从 v1 到 v2 的一条欧拉路径 P 那么我们需要加入一些重边使得图中的所有点入度等于出度。最优方案是找到一条从 v2 到 v1 的最短路 Q 将 P 与 Q 拼接就得到了一条符合要求的路线。
通过以上的分析可以看出本题的实质是在图 G 中增加一些重复边使新图的每个点入度等于出度并且增加的重复边总边权和最小。我们先对每个点 u 求出入度减去出度的值 s(u) 。如果将一条边 (u, v) 重复一次就会使得 s(u) 减小 1 而 s(v) 增加 1 同时产生边权的代价。这就是一个多源汇的最小费用最大流模型。具体的建图方式如下对于点 u 若s(u) 0 则从源点向 v 连容量为 |s(u)| 费用为 0 的边若 s(u) 0 则从 u 向汇点连容量为 |s(u)| 费用为 0 的边。对于每条图 G 中的有向边 (u, v) 则从 u 向 v 连一条容量为正无穷费用为该边边权的边。求出该图源点到汇点的最小费用最大流。若在源点连出的 边中存在未满流的边则图 G 不存在每条边至少经过一次的回路。
若存在方案图G的边权和加上求出的最小费用就是该方案的总边权。对于每条边 (u, v)对应的边在最大流中的流量就是该边需要额外重复的次数。可以利用有向图欧拉回路算法求出符合要求的路径。
由于该题和上一题的代码相差不大就不再加以详细的叙述了。
我们可以对应地给出该问题的无向图版本可以通过同样的方式分析此题。
问题 5.4. 给定无向带权连通图 G (V, E) 求出一条总边权和最小的回路使得经过每一条边至少一次。
解法. 无向图可以类比有向图的解法。我们要在图 G 中增加一些重复边使新图的每个点都成为偶顶点并且增加的重复边总边权和最小。若图中有 2k 个奇顶点则我们要加入 k条以奇顶点为端点路径。每个点最多只会为一条路径的端点否则我们可以将两条路径合并为一条。
每一条路径必然选取两个端点间的最短路。因此我们需要将 2k 个奇顶点分为k 对使得每对点的最短路长度之和最小。我们要求出一个最小权完美匹配这可以通过一般图最小权完美匹配算法求解。由于本人实力有限不会带权带花树所以等以后再来填坑把
6 欧拉图相关的计数
计数问题是图论中一类重要的问题。欧拉图代表了点度为偶以及连通这两个条件。 两个简单的条件却产生了很多有趣的计数问题。在本节的介绍过程中我们将会利用上文 中得到的欧拉图的相关性质构造有利于我们求解的模型最后使用我们熟知的方法得到 答案。 我们将通过几个经典的例子探究欧拉图相关的计数问题的常用方法并提出一些 有用的结论。
本章是最难的一章前四题已经达到了洛谷较难的蓝题和紫题的难度后面的三道题也绝对有顶级难度的紫题甚至黑题的难度。我也只能以提供代码为主了。
6.1 欧拉图计数
问题6.1
caioj2534 无向图计数 【题目描述】 给定 n 求包含 n 个点的所有点度为偶数的有标号简单无向图个数。 【输入格式】 仅一行输入一个整数n 【输出格式】 仅一行输出一个整数表示包含 n 个点的所有点度为偶数的有标号简单无向图个数。 最后的结果记得 mod 10^97 【输入样例1】 1 【输出样例1】 1 【输入样例2】 2 【输出样例2】 1 【输入样例3】 3 【输出样例3】 2 【数据范围】 1n2*10^9 【提示】 不含平行边也称重边也不含自环的图称为简单图
解法. 为了方便表示记 s n s_n sn 表示 n 个点所有点度为偶数的有标号简单无向图个数。除去 n号点以及 n 号点关联的边此时其余这 n − 1 个点中必然有偶数个奇顶点那么 n 号点就必须与这偶数个奇顶点各连一条边。我们只需求 n − 1 个点包含偶数个奇顶点的简单无向图的个数。而任意一个无向图中奇顶点的个数一定是偶数 s n s_n sn 就是 n − 1 个点简单无向图的数量。 因为n-1个点之间有 C n − 1 2 C_{n-1}^2 Cn−12个位置可以连边形象理解就是 n ∗ ( n − 1 ) / 2 n*(n-1)/2 n∗(n−1)/2所以 s n 2 C n − 1 2 s_n2^{C_{n-1}^2} sn2Cn−12。
参考代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
const LL P1e97;
LL ksm(LL a,LL b){LL ans1;while(b){if(b1)ans(LL)ans*a%P;a(LL)a*a%P;b1;}return ans;
}
LL inv[21];
LL C(LL y,LL x){if(y0||x0||yx)return 0;y%P;if(!y||!x)return 1;LL ans1;for(int i0;ix;i)ans(LL)ans*(y-i)%P;for(int i1;ix;i)ans(LL)ans*inv[i]%P;return ans;
}
int main(){LL n;cinn;for(int i1;i11;i)inv[i]ksm(i,P-2);printf(%lld\n,ksm(2,C(n-1,2)));return 0;
}
问题6.2
caioj2535 【题目描述】 给定 n 求包含 n 个点的有标号简单连通无向欧拉图个数。 【输入格式】 仅一行输入一个整数n 【输出格式】 仅一行输出一个整数表示包含 n 个点的欧拉图个数。 最后的结果记得 mod 10^97 【输入样例1】 1 【输出样例1】 1 【输入样例2】 2 【输出样例2】 0 【输入样例3】 3 【输出样例3】 4 【数据范围】 1n2000
解法. 记 f n f_n fn 为问题所求的 n 个点的有标号简单连通无向欧拉图个数。同时处理连通与度为偶数两个约束较为困难但我们在前面已经解决了度为偶数的问题。接下来我们利用容斥原理的思路解决连通这一限制。 f n f_n fn 等于 s n s_n sn 减去不连通的方案数。而不连通的方案数可以通过枚举 1 号点所在连通分量大小计算。当连通分量大小为 i 时该连通分量内点的集 合有 C n − 1 i − 1 C_{n-1}^{i-1} Cn−1i−1 种不同组合方式这些点之间的连边方法有 f i f_i fi 种剩余点之间就不需要保证连通 性了有 s n − i s_{n−i} sn−i 种连边方法。公式如下 f n s n − ∑ i 1 n − 1 C n − 1 i − 1 f i s n − i f_ns_n-\sum_{i1}^{n-1}C_{n-1}^{i-1}f_is_{n-i} fnsn−i1∑n−1Cn−1i−1fisn−i 运用该递推公式可以在 O ( n 2 ) O(n^2) O(n2) 的时间内求出答案。当然也可以运用CDQ分治FFT或 是多项式求逆等优化技巧得到 O ( n l o g 2 n ) O(n log^2n) O(nlog2n) 或 O ( n l o g n ) O(n log n) O(nlogn) 的更高效率的解法。 由于本人能力有限仅能写出朴素算法
参考代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
const LL P1e97;
const int N2e310;
LL ksm(LL a,LL b){LL ans1;while(b){if(b1)ans(LL)ans*a%P;a(LL)a*a%P;b1;}return ans;
}
LL inv[N],s[N],C[N][N],f[N];
//C[i][j]表示i选j个数的组合总数
int main(){for(int i1;i2000;i)inv[i]ksm(i,P-2);C[1][0]C[1][1]1;for (int i2;i2000;i){C[i][0]1;for(int j1;j2000;j)C[i][j](C[i-1][j]C[i-1][j-1])%P;}for(int i1;i2000;i)s[i]ksm(2,C[i-1][2]);LL n;cinn;for(int i1;in;i){f[i]s[i];LL sum0;for(int j1;jn-1;j)sum(sumC[i-1][j-1]*f[j]%P*s[i-j]%P)%P;f[i](f[i]P-sum)%P;}printf(%lld\n,f[n]);return 0;
}6.2 欧拉子图计数
问题6.3
caioj2536 【题目描述】 给定一个无向连通图 G (V, E) 求有多少个支撑子图G’(V,E’),E’属于E满足每个点的度都是偶数。 该无向图含有n个点m条边。 最后的结果mod 1e97 【输入格式】 第1行输入两个整数n,m 第2-m1行每行输入两个整数x,y表示边 【输出格式】 输出满足条件的支撑子图的总数 mod 1e97 【输入样例】 4 4 1 2 2 3 1 3 3 4 【输出样例】 2 【数据范围】 对于40%的数据满足1n200,1m400,且nm-1 对于100%的数据满足1n,m10^6,且nm-1
这个图论问题不好直接入手我们可以将这个问题可以转化为代数问题。用变量表 示每条边选或不选再把度的约束转化为等式这样可以列出一组方程描述此问题。对于 标号为 i 的边这条边是否出现在子图中用 0/1 变量 xi 表示。对于点 v 与 v 关联的边分 别为 e 1 , e 2 , . . . , e d e_1, e_2, ..., e_d e1,e2,...,ed这些边在子图中出现的条数必为偶数得到 x e 1 x o r x e 2 x o r . . . x o r x e d x_{e_1} xor x_{e_2} xor ... xor x_{e_d} xe1xorxe2xor...xorxed 0 其中 xor 表示异或运算。由此我们得到了 n 个等式 m 个变量的异或方程组。通过高斯消 元算法我们可以求出该方程组的自由元的数量s 则满足题意的子图数量为 2 s 2^s 2s 。这一解 法的时间复杂度为 O ( n 2 m ) O(n^2m) O(n2m) 。
上述方法虽然已经解决了本问题但在转化为代数模型的过程中我们忽略了一些图自身的性质例如图 G 是连通的每一条边所代表的变量只在方程组中出现了两次。那么我们能否利用这些性质得到更简便的解法呢
我们任意求出图 G 的一棵生成树将该生成树上的边对应的变量作为主元此时非树边所对应的变量恰为自由元。我们可以找到这一过程的组合意义。依次决定每条非树边是否选择容易发现对于一组非树边的选法树边只有唯一的选法。 我们任意指定一个点为根按照从叶子到树根的顺序依次决定每个点与其父亲间的树边是否选择。 所以一组非树边变量的取值就对应了一组方程的解。 事实上若把一条非树边与其两端点在树上的路径看做该树边所代表的环将所有选择的非树边代表的环异或一条边出现奇数次则选择否则不选择就得到了一个满足条件的子图。我们可以很容易表示出满足条件的子图的数量为 2 m − n 1 2^{m−n1} 2m−n1。
辅助解释 因为题目只是说点的度数为偶数并没有要求存在欧拉回路。所以我们可以构建任意一颗生成树一共用掉n-1条边。因为一组非树边都对应了唯一一组树边且一定存在树边能够使得每个点度都是偶数。所以一共有 2 m − ( n − 1 ) 2^{m-(n-1)} 2m−(n−1)即 2 m − n 1 2^{m-n1} 2m−n1种情况。 还有一种解释就是直接从方程式入手。对于一个n*m的方程组且每条边只会出现两次所以高斯消元以后一定会剩余(m-n1)个自由元所以结果一定是 2 m − n 1 2^{m-n1} 2m−n1与内部连接方式无关。
参考代码
#includeiostream
using namespace std;
typedef long long LL;
const LL P1e97;
LL n,m;
LL power(LL a,LL b){LL ans1;while(b){if(b1)ansans*a%P;aa*a%P;b1;}return ans;
}
int main(){cinnm;coutpower(2,m-n1)endl;return 0;
}我们还可以将该问题扩展到一般的无向图
问题6.4
caioj2537 【题目描述】 给定一个无向图不一定连通G (V, E) 求有多少个支撑子图G’(V,E’),E’属于E满足每个点的度都是偶数。 该无向图含有n个点m条边。 最后的结果mod 1e97 【输入格式】 第1行输入两个整数n,m 第2-m1行每行输入两个整数x,y表示边 【输出格式】 输出满足条件的支撑子图的总数 mod 1e97 【输入样例】 4 4 1 2 2 3 1 3 3 4 【输出样例】 2 【数据范围】 对于40%的数据满足1n200,1m400 对于100%的数据满足1n,m10^6
解法. 容易发现不同的连通分量之间是独立的。若图的连通分量数量为 c 对每一个连 通分量使用上述公式得到满足顶点为度为偶数的支撑子图数量为 2 m − n c 2^{m−nc} 2m−nc 。可以发现这一数值与每一连通分量内部边的连接方式无关在 O(n m) 的时间内就可以求出 c 计算出本题的答案。
参考代码
#includeiostream
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#define il inline
#define dg isdigit
#define gc getchar()
using namespace std;
templatetypename Til void read(T x){x0;int f0;char sgc;while(!dg(s))f|s-,sgc;while( dg(s))xx*10s-48,sgc;xf?-x:x;
}
typedef long long LL;
const LL P1e97;
int n,m;
LL Power(LL a,LL b){LL ans1;while(b){if(b1)ansans*a%P;aa*a%P;b1;}return ans;
}
const int N1e610;
struct edge{int v,nxt;
}e[N1];int tot,last[N];
il void Addedge(int u,int v){e[tot](edge){v,last[u]};last[u]tot;e[tot](edge){u,last[v]};last[v]tot;
}
bool vis[N];int num0;
void dfs(int u){vis[u]1;num;for(int ilast[u];i;ie[i].nxt){int ve[i].v;if(!vis[v])dfs(v);}
}
int main(){read(n),read(m);int c0,last;for(int i1;im;i){int u,v;read(u),read(v);Addedge(u,v);}for(int i1;in;i)if(!vis[i]){lastnum;dfs(i);if(last1num)c;else if(last1num)num--;}coutPower(2,m-numc)endl;return 0;
}
6.3 欧拉回路计数
问题6.5 caioj2538 【题目描述】 .给定一个有向欧拉图 G (V, E) 求以1号点为起点的欧拉路径的数量。 结果记得mod 10^97 【输入格式】 第一行两个整数n,m表示该欧拉图的点数和边数。 接下来m行每行两个整数x,y表示一条有向边。 【输出格式】 输出一个整数表示求以1号点为起点的欧拉路径的数量mod 10^97后的值。 【输入样例】 3 6 1 2 1 2 2 3 2 3 3 1 3 1 【输出样例】 8 【数据范围】 1n500,1m200000
解法 我们先提出一种构造方案。找到一棵以1号点为根的内向树即每个点有唯一的一条路径到达1号点对于一个点的所有不再树上的出边指定一个顺序。接下来我们来证明上述方案与欧拉路径一一对应。
先证明一个方案唯一对于一条欧拉路径。对于一个方案我们从1号点出发对于每一个点按照非树边指定的顺序走这条路径就是一条欧拉路径。回顾Fleury算法的执行过程只需证明走一条非树边 (u, v) 的时候 u 与 v 在树上是弱连通的。如果一个点有未访问的出边则这个点出发的树边一定未访问过。走一条非树边 (u, v) 的时候 u 与 v 的树边都未访问过它们的父亲节点出发的树边一定也未访问过。以此类推它们到根节点的路径的每一条边都未访问过。因此走一条非树边 (u, v) 的时候 u 与 v 在树上是弱连通的。按照上述方式得到的路径一定是欧拉路径。
再证明一条欧拉路径唯一对应一个方案。对于以 1 号点为起点和终点的欧拉路径除1 号点外的每个点最后访问的出边是“树边”其余出边按照访问次序确定顺序便得到一个上述方案。需要证明得到 n − 1 条“树边”中不存在环。我们可以反证假设“树边”形成了环由于 1 号节点不选择树边环上不存在一号节点。我们任选环上一点出发沿着“树边”走最后又回到了这个点。因为树边为最后访问的一条边因此欧拉路径终止于该点了这与欧拉路径的终点为 1 号点矛盾。这样我们就证明了方案与欧拉路径一一对应。接下来我们来考虑“方案”的数量。对 于图 G 记 Ti 为以 i 为根的内向树的数量 di 为 i 号点的出度。对于一棵内向树与1 号点关联的出边有 d1! 种其余节点 i 对非树边指定顺序有 di! 种。以 1 号点为起点和终点的欧拉路径的数量为 T 1 d 1 ∏ i 2 n ( d i − 1 ) ! T_1d_1 \prod_{i2}^n(d_i-1)! T1d1i2∏n(di−1)! 其中 T1 可以利用矩阵树定理求出。即出度矩阵减去邻接矩阵去掉第一行第一列后行列 式的值。时间复杂度为 O(n^3) 。
参考代码
#includecstdio
#includecstring
#includecstdlib
#includeiostream
#includealgorithm
#define il inline
#define gc getchar()
#define dg isdigit
using namespace std;
templatetypename Til void read(T x){x0;int f0;char sgc;while(!dg(s))f|s-,sgc;while( dg(s))xx*10s-48,sgc;xf?-x:x;
}
const int N5e210,M2e510;
const int P1e97;
typedef long long LL;
int power(int a,int b){int ans1;for(;b;b1,a(LL)a*a%P)if(b1)ans(LL)ans*a%P;return ans;
}
int n,m,a[N][N],b[N][N],jc[M],d[M];
int gauss(){int k1,ff1,ans1;for(int i1;in;i){int nowk;while(nown!(a[now][i]))now;if(nown1)continue;if(now!k)ff*-1;for(int j1;jn;j)swap(a[now][j],a[k][j]);for(int invpower(a[k][i],P-2),ji1;jn;j)for(int t(LL)a[j][i]*inv%P,p1;pn;p)a[j][p](a[j][p]-(LL)a[k][p]*t%PP)%P;k;}for(int i1;in;i)ans(LL)ans*a[i][i]%P;if(ff-1)return P-ans;else return ans;
}
int main(){
// freopen(5.in,r,stdin);
// freopen(5.out,w,stdout);read(n),read(m);for(int x,y,i1;im;i){read(x),read(y);d[x];a[y][x]--,a[x][x];}for(int i1;in;i)for(int j1;jn;j)b[i][j]a[i][j];for(int i1;in;i)for(int j1;jn;j)a[i][j]b[i1][j1];n--;int ansgauss();jc[0]1;for(int i1;im;i)jc[i](LL)jc[i-1]*i%P;ans(LL)ans*jc[d[1]]%P;n;for(int i2;in;i)ans(LL)ans*jc[d[i]-1]%P;printf(%d\n,ans);return 0;
}问题6.6
caioj2539 【题目描述】 .给定一个有向欧拉图 G (V, E) 求欧拉回路的数量。 结果记得mod 10^97 【输入格式】 第一行两个整数n,m表示该欧拉图的点数和边数。 接下来m行每行两个整数x,y表示一条有向边。 【输出格式】 输出一个整数表示欧拉回路的数量mod 10^97后的值。 【输入样例】 3 6 1 2 1 2 2 3 2 3 3 1 3 1 【输出样例】 4 【数据范围】 1n500,1m200000
我们可以通过同样的方式求出不同欧拉回路的数量即不考虑起点路径循环同构。 为了避免重复计算同一种欧拉回路我们需要将一个欧拉回路转化为唯一的一条欧拉路径 即从 1 号点出发的标号最小的边作为第一条访问边。我们就能够得到不同的欧拉回路的数 量 T 1 ∏ i 1 n ( d i − 1 ) ! T_1 \prod_{i1}^n(d_i-1)! T1i1∏n(di−1)!
#includecstdio
#includecstring
#includecstdlib
#includeiostream
#includealgorithm
#define il inline
#define gc getchar()
#define dg isdigit
using namespace std;
templatetypename Til void read(T x){x0;int f0;char sgc;while(!dg(s))f|s-,sgc;while( dg(s))xx*10s-48,sgc;xf?-x:x;
}
const int N5e210,M2e510;
const int P1e97;
typedef long long LL;
int power(int a,int b){int ans1;for(;b;b1,a(LL)a*a%P)if(b1)ans(LL)ans*a%P;return ans;
}
int n,m,a[N][N],b[N][N],jc[M],d[M];
int gauss(){int k1,ff1,ans1;for(int i1;in;i){int nowk;while(nown!(a[now][i]))now;if(nown1)continue;if(now!k)ff*-1;for(int j1;jn;j)swap(a[now][j],a[k][j]);for(int invpower(a[k][i],P-2),ji1;jn;j)for(int t(LL)a[j][i]*inv%P,p1;pn;p)a[j][p](a[j][p]-(LL)a[k][p]*t%PP)%P;k;}for(int i1;in;i)ans(LL)ans*a[i][i]%P;if(ff-1)return P-ans;else return ans;
}
int main(){read(n),read(m);for(int x,y,i1;im;i){read(x),read(y);d[x];a[y][x]--,a[x][x];}for(int i1;in;i)for(int j1;jn;j)b[i][j]a[i][j];for(int i1;in;i)for(int j1;jn;j)a[i][j]b[i1][j1];n--;int ansgauss();jc[0]1;n;for(int i1;im;i)jc[i](LL)jc[i-1]*i%P;for(int i1;in;i)ans(LL)ans*jc[d[i]-1]%P;printf(%d\n,ans);return 0;
}
问题6.7
caioj2540 【题目描述】 .给定一个有向半欧拉图 G (V, E) 求欧拉路径的数量。 结果记得mod 10^97 【输入格式】 第一行两个整数n,m表示该欧拉图的点数和边数。 接下来m行每行两个整数x,y表示一条有向边。 【输出格式】 输出一个整数表示求以1号点为起点的欧拉路径的数量mod 10^97后的值。 【输入样例】 3 5 2 2 1 3 2 2 3 2 2 2 【输出样例】 6 【数据范围】 1n500,1m200000
解法. 对于不好处理的半欧拉图问题最直接的办法就是通过加边转化为欧拉图问题。我 们在半欧拉图中添加一条有向边将半欧拉图 G 变为欧拉图 G‘。那么图 G’中的欧拉回 路就与图 G 中的欧拉路径一一对应。利用BEST定理给出的公式计算图 G‘的欧拉回路的 数量就可以算出图 G 的欧拉路径的数量。
参考代码
#includecstdio
#includecstring
#includecstdlib
#includeiostream
#includealgorithm
#define il inline
#define gc getchar()
#define dg isdigit
using namespace std;
templatetypename Til void read(T x){x0;int f0;char sgc;while(!dg(s))f|s-,sgc;while( dg(s))xx*10s-48,sgc;xf?-x:x;
}
const int N5e210,M2e510;
const int P1e97;
typedef long long LL;
int power(int a,int b){int ans1;for(;b;b1,a(LL)a*a%P)if(b1)ans(LL)ans*a%P;return ans;
}
int n,m,a[N][N],b[N][N],jc[M],d[N],d2[N];
int gauss(){int k1,ff1,ans1;for(int i1;in;i){int nowk;while(nown!(a[now][i]))now;if(nown1)continue;if(now!k)ff*-1;for(int j1;jn;j)swap(a[now][j],a[k][j]);for(int invpower(a[k][i],P-2),ji1;jn;j)for(int t(LL)a[j][i]*inv%P,p1;pn;p)a[j][p](a[j][p]-(LL)a[k][p]*t%PP)%P;k;}for(int i1;in;i)ans(LL)ans*a[i][i]%P;if(ff-1)return P-ans;else return ans;
}
int main(){read(n),read(m);int S,T;for(int x,y,i1;im;i){read(x),read(y);d[x];d2[y];a[y][x]--,a[x][x];}for(int i1;in;i){if(d[i]d2[i])continue;if(d[i]-d2[i]1)Si;else if(d2[i]-d[i]1)Ti;}//T - S xT ySa[S][T]--,a[T][T],d[T];for(int i1;in;i)for(int j1;jn;j)b[i][j]a[i][j];for(int i1;in;i)for(int j1;jn;j)a[i][j]b[i1][j1];n--;int ansgauss();jc[0]1;n;for(int i1;im;i)jc[i](LL)jc[i-1]*i%P;for(int i1;in;i)ans(LL)ans*jc[d[i]-1]%P;printf(%d\n,ans);return 0;
}
7 总结
欧拉图问题是图论中十分重要的一类问题。本文从欧拉图本质分析着手介绍了欧拉 图的判定方法和欧拉回路的生成算法。在分析性质和设计算法的过程中图的连通性与顶 点的度起到了关键的作用这两个要素是我们分析欧拉图问题的基础。以这两个要素入手 我们总结出了更一般的结论与解题思路。
运用欧拉图模型可以解决一些应用问题。本文分析了两种常见的解题思路。一是对于 表面上看似是哈密尔顿问题的题目不妨考虑一下将边与点的关系对调转化为欧拉图问 题。二是对于构造或贪心难以处理的欧拉图生成问题可以考虑将约束转化为网络流模型 或其它经典问题。模型转化往往是这类题目的突破口。
欧拉图的计数问题与生成问题类似需要灵活运用模型转化基于欧拉图性质分析 构造组合意义抽象出代数模型并且善用计数技巧进行解决。
总而言之深入理解欧拉图相关性质灵活运用模型转化巧妙借助其他知识与算法 是解决欧拉图相关问题的关键。希望本文可以起到抛砖引玉的作用使更多人了解并继续 发掘欧拉图问题的奥秘。
