一笔画问题.docx
- 文档编号:7959424
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:14
- 大小:18.80KB
一笔画问题.docx
《一笔画问题.docx》由会员分享,可在线阅读,更多相关《一笔画问题.docx(14页珍藏版)》请在冰点文库上搜索。
一笔画问题
2014-7-15一笔画问题简单学习总结
今天学的还是图论的内容——一笔画问题。
一笔画就是把一个无向图(或有向图)所有的边都遍历一遍且不重复走同样的边。
这个新知识的算法都是建立在几个数学性质上面的,分别如下:
1、这个有向图(或无向图)必须是连通的。
这是最基本的条件。
2、每个点之间度的要求:
无向图:
满足①所有点的度数为偶数或者②有两个点度数为奇数,其他点度数为偶数,且这两个奇数点必须为一笔画中的开端和结尾。
有向图:
满足①所有点出入度相等或者②有一个点出度比入度大1,另一个点入度比出度大1,其他点的出入度相等,且出度大的点为一笔画开端,入度大的点为一笔画结尾。
数学简单证明还是比较容易的,如果一个点度数为奇数,那么从该点出发,去到的无非就两种情况:
偶点或奇点,偶点我们总可以绕一个圈回到该偶点重新出发。
奇点就到达终点了。
(圈套圈的思路)
对于无向边,有一个特殊处理:
无向边路过一条边后,要把它的反向边去掉。
这个过程可以用指针实现,用一个指针指向它的反向边。
或者,如果用数组来储存边时,因为反向边是同时申请的,所以它们的下标一定是相邻的,可以用异或操作得到。
下面介绍几种算法:
1、圈套圈算法
算法思想:
每次在某个点随便找一条边,一直走,如果找到环,那么就相应地插入到一笔画的顺序中,环中若有嵌套环,那么同样地找下去。
算法实现:
可以用链表实现插入之类的操作,但若用深搜回溯写的话,程序会非常简单。
就是从奇点(或任意点)出发,任意地深度遍历,如果当前点已经不能往下搜,那么就回溯看祖先节点是否有其他可以遍历的点,按回溯的顺序弹出的边,在无向图里面正反顺序都是一笔画正确解法,有向图里需要取反顺序。
算法优化:
由于系统栈的空间局限性,在朴素的递归算法里面不能支持较大数据范围的题目,可以改成用stack栈模拟递归的操作,这样就不再会爆栈。
2、弗罗莱算法
算法思想:
首先在奇点出发,尽量先不走桥(若去掉该边图不连通,则该边为桥),先走环路。
只要顺序地走一遍就是一笔画解法。
算法实现:
判断一边是否为桥的方法是按照定义,去掉改边后,用宽度搜索遍历一遍。
如何判断一个图是否能实现一笔画?
根据上述一笔画所需的条件性质,我们可以做一次BFS判断该图是否连通。
值得注意的是,当一些点如A、B未在读入出现过时,一切操作和判断应该略过这些点,因为这些点根本没有在图中。
同时,判断奇数点是否只有两个或者没有,否则不能实现一笔画。
做了三道练习题,题目的变形比较小,但还是有许多值得注意的细节。
第一题《多米诺》
题目大意:
给出一些多米诺骨牌(1*2的方块),左右面都有一个0~6的数字。
你可以任意调整这些骨牌的相对顺序,还可以旋转它们,要求使得这些骨牌数字首尾相连(类似于单词接龙)
题目分析:
首先建一个图,图的点最多有7个(0~6),根据多米诺骨牌上的内容在两个数字之间建边,由于可以旋转,所以这边应该是无向边。
构图完毕后,便是求一笔画问题的顺序。
最后输出摆放和旋转情况即可(任一解即可)(可能无解)
这个程序写得不是很好,模块化程度不够,链接矩阵使用较随意,链表写得复杂,最后输出边的编号时效率太低。
需要改正。
程序如下:
#include
#include
#include
usingnamespacestd;
structNode
{
Node*nex;
intnp;
Node(){nex=NULL;np=0;}
};
Nodespace[1024];
intn,iSpace=0;
intcnt[7];
Node*hea[10],*tai[10];
intans[1024],m=0;
intadj[10][10];
intgpa[102],gpb[102];
Node*getNew(){return&space[iSpace++];}
voidpushback(inta,intb)
{
if(tai[a]==NULL)
{
tai[a]=hea[a]=getNew();
tai[a]->np=b;
}
else
Node*A=getNew();
A->np=b;
tai[a]->nex=A;
tai[a]=A;
}
}
voidwork(intst);
queue
boolvis[7];
boolused[102];
boolcheck(ints)
{
q.push(s);
vis[s]=true;
while(!
q.empty())
{
intnow=q.front();
q.pop();
for(Node*i=hea[now];i!
=NULL;i=i->nex)
{
intNex=i->np;
if(!
vis[Nex])
{
q.push(Nex);
vis[Nex]=true;
}
}
}
for(inti=0;i<=6;++i)if(cnt[i]!
=0&&vis[i]==false)returnfalse;
returntrue;
}
intmain()
{
memset(cnt,0,sizeof(cnt));
memset(adj,0,sizeof(adj));
cin>>n;
ints=1;
for(inti=1;i<=n;++i)
inta,b;
cin>>a>>b;
gpa[i]=a;gpb[i]=b;
cnt[a]++;cnt[b]++;
pushback(a,b);
pushback(b,a);
adj[a][b]++;adj[b][a]++;
s=a;
}
intst=s,len=0;
for(inti=0;i<=6;++i)
if(cnt[i]%2==1)
{
st=i;
len++;
}
if(len==1||len>2||!
check(s))cout<<"Nosolution"< else { work(st); for(inti=1;i<=m;i+=2) { inta=ans[i]; intb=ans[i+1]; for(intj=1;j<=n;++j) { if(used[j]==true)continue; if(gpa[j]==a&&gpb[j]==b) { cout< used[j]=true; break; } elseif(gpa[j]==b&&gpb[j]==a){ cout< used[j]=true; break; } } } } system("pause"); return0; } voidwork(intst) { for(Node*i=hea[st];i! =NULL;i=i->nex) { intj=i->np; if(adj[st][j]==0)continue; adj[st][j]--;adj[j][st]--; work(j); ans[++m]=st; } ans[++m]=st; } 第二题《单词接龙》 题目大意: 给你一些单词,让你首尾串起来串成一串,并且输出一个字典序最小的方案。 题目分析: 和上面的多米诺骨牌一样,区别在于单词不能旋转,所以构图要改为有向边,相应地,判断时就要区分出入度的区别。 字典序最小,我们可以通过给链接链表的边排序,这样访问时就会优先搜索到字典序小的边。 除此之外,我们在确定起点时,除了奇点的情况,偶点必须找到字典序最小的点作为起点。 程序如下: 采用非递归的栈模拟写法,模块程度较高。 #include #include #include #include #include #include #include usingnamespacestd; constintmaxn=1024; structEdge { intnex; intedgP; Edge(){nex=edgP=0;} Edge(inta,intb){nex=a;edgP=b;}}; stringwords[maxn]; intn; intind[30],outd[30]; queue boolvis[30]; vector vector stack voidinit(); boolcmp(Edgea,Edgeb); boolbfs(); intcheck(); voidStack_DFS(intst); voidprint_ans(); intmain() { //freopen("B.in","r",stdin); intT; cin>>T; for(inti=0;i! =T;++i) { init(); intst=check(); if(st==-1)cout<<"***"< else { Stack_DFS(st); print_ans(); } } system("pause"); return0; } boolcmp(Edgea,Edgeb) { returnwords[a.edgP] } voidinit() { memset(ind,0,sizeof(ind)); memset(outd,0,sizeof(outd)); for(inti=1;i<=26;++i)edg[i].clear(); cin>>n; for(inti=0;i! =n;++i) { stringst; cin>>st; words[i]=st; inta=int(st[0])-96; intb=int(st[st.size()-1])-96; outd[a]++;ind[b]++; edg[a].push_back(Edge(b,i)); } for(inti=1;i<=26;++i) sort(edg[i].begin(),edg[i].end(),cmp); } boolbfs(intst) { memset(vis,false,sizeof(vis)); q.push(st); vis[st]=true; while(! q.empty()) { intnow=q.front(); q.pop(); for(inti=0;i! =edg[now].size();++i) { intNex=edg[now][i].nex; if(! vis[Nex]) { q.push(Nex); vis[Nex]=true; } } } for(inti=1;i<=26;++i) if((ind[i]! =0||outd[i]! =0)&&vis[i]==false)return false; returntrue; } intcheck() { intlen=0,st=-1; for(inti=1;i<=26;++i) { if(ind[i]-outd[i]>1||outd[i]-ind[i]>1)return-1; if(ind[i]! =outd[i]) { len++; if(outd[i]>ind[i])st=i; } elseif(ind[i]! =0&&st==-1)st=i; } if(len==1||len>2||! bfs(st))return-1; returnst; } intadj[30]; voidStack_DFS(intst) { ans.clear(); memset(adj,0,sizeof(adj)); point.push(st); edge.push(-1); while(! point.empty()) { intx=point.top(); if(adj[x]==edg[x].size()) { point.pop(); ans.push_back(edge.top()); edge.pop(); continue; } intp=adj[x]; inty=edg[x][p].nex; intz=edg[x][p].edgP; adj[x]++; point.push(y); edge.push(z); } } voidprint_ans() { for(inti=ans.size()-2;i>=0;--i) { if(i! =0)cout< elsecout< } cout< } 第三题《单词接龙简化》 题目大意: 题目中给你n个字符串,问你能不能找到一种排列方案,使前一个单词的尾部字符是下一个单词的首部字母。 题目分析: 由于只需要判断是否能达成一笔画问题,而不需要打印方案,我们的DFS程序可以省去,只需要做出入度的判断和图是否连通的操作即可。 由于是多组数据,程序的初始化非常重要,建议把所有改动过的数据统一初始化,免得漏掉出错。 程序如下: #include #include #include #include usingnamespacestd; structNode { Node*nex; intnp; }; Nodespace[802000]; intn,iSpace=0; charstr[1024]; stringstr1; intcntr[30],cnto[30]; Node*hea[30],*tai[30]; Node*getNew(){return&space[iSpace++];} voidpushback(inta,intb) { if(tai[a]==NULL) { hea[a]=tai[a]=getNew(); tai[a]->np=b; } else { Node*A=getNew(); A->np=b; tai[a]->nex=A; tai[a]=A; } } queue intvis[31]; boolcheck(intst) { memset(vis,0,sizeof(vis)); q.push(st); vis[st]=true; while(! q.empty()) { intnow=q.front(); q.pop(); for(Node*i=hea[now];i! =NULL;i=i->nex) { intNex=i->np; if(! vis[Nex]) { q.push(Nex); vis[Nex]=true; } } } for(inti=1;i<=26;++i)if(cntr[i]! =0&&vis[i]==false)returnfalse; returntrue; } intmain() { freopen("c.in","r",stdin); intT; scanf("%d",&T); intst; for(inti=0;i! =T;++i) { //iSpace=0; memset(cntr,0,sizeof(cntr)); memset(cnto,0,sizeof(cnto)); for(intj=0;j<=29;++j)hea[j]=tai[j]=NULL; scanf("%d",&n); for(intj=1;j<=n;++j) { scanf("%s",str); str1=str; inta=int(str[0])-96; intb=int(str[str1.size()-1])-96; cnto[a]++;cntr[b]++; pushback(a,b); //pushback(b,a); st=a; } intlen=0; for(inti=1;i<=26;++i) { if(cntr[i]! =cnto[i]) { if(cnto[i]>cntr[i])st=i; len++; } if(cntr[i]-cnto[i]>1||cnto[i]-cntr[i]>1) len+=10; } if(len==1||len>2||! check(st))printf("Thedoorcannotbeopened.\n"); elseprintf("Orderingispossible.\n"); } system("pause"); return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 笔画 问题