- 浏览: 390622 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
给出你n个单词,如果一个单词的尾部和另一个单词的头部相同那么这两个单词就能连在一起(比如‘abc’和‘cde’就能够连成abc-cde),如果这个单词后面的数字是1,则代表这个单词的逆序也是一个单词,可以翻转过来。求所有单词能不能连成一长串。
大致思路:
转化为混合图的欧拉回路,把字母当作节点。注意要用并查集来检测图是否连通。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int inf=1<<30; const int nMax=2000; const int mMax=100000; class node{ public: int c,u,v,next; };node edge[mMax]; int ne, head[nMax]; int cur[nMax], ps[nMax], dep[nMax]; void addedge(int u, int v,int w){ ////dinic邻接表加边 // cout<<u<<" add "<<v<<endl; edge[ne].u = u; edge[ne].v = v; edge[ne].c = w; edge[ne].next = head[u]; head[u] = ne ++; edge[ne].u = v; edge[ne].v = u; edge[ne].c = 0; edge[ne].next = head[v]; head[v] = ne ++; } int dinic(int s, int t){ // dinic int tr, res = 0; int i, j, k, f, r, top; while(1){ memset(dep, -1, sizeof(dep)); for(f = dep[ps[0]=s] = 0, r = 1; f != r;) for(i = ps[f ++], j = head[i]; j; j = edge[j].next) if(edge[j].c && dep[k=edge[j].v] == -1){ dep[k] = dep[i] + 1; ps[r ++] = k; if(k == t){ f = r; break; } } if(dep[t] == -1) break; memcpy(cur, head, sizeof(cur)); i = s, top = 0; while(1){ if(i == t){ for(tr =inf, k = 0; k < top; k ++) if(edge[ps[k]].c < tr) tr = edge[ps[f=k]].c; for(k = 0; k < top; k ++){ edge[ps[k]].c -= tr; edge[ps[k]^1].c += tr; } i = edge[ps[top=f]].u; res += tr; } for(j = cur[i]; cur[i]; j = cur[i] =edge[cur[i]].next){ if(edge[j].c && dep[i]+1 == dep[edge[j].v]) break; } if(cur[i]){ ps[top ++] = cur[i]; i = edge[cur[i]].v; } else{ if(top == 0) break; dep[i] = -1; i = edge[ps[-- top]].u; } } } return res; } char str[30]; int in[nMax]; int out[nMax]; bool vis[nMax]; int p[nMax],r[nMax]; int find(int a){ if(p[a]!=a){ p[a]=find(p[a]); } return p[a]; } void unionset(int i,int j){ i=find(i); j=find(j); if(i!=j){ if(r[i]>r[j]){ p[j]=i; } else{ p[i]=j; if(r[i]==r[j]){ r[i]++; } } } } int main(){ int i,j,k,cas,a,b,n,f,len,flag,s,t,sum; scanf("%d",&cas); for(int ii=1;ii<=cas;ii++){ s=27,t=28; ne=2; flag=1; memset(head,0,sizeof(head)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(vis,0,sizeof(vis)); for(i=0;i<100;i++)p[i]=i,r[i]=0; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%s%d",str,&f); len=strlen(str); in[str[len-1]-'a']++; out[str[0]-'a']++; vis[str[0]-'a']=vis[str[len-1]-'a']=1; unionset(str[len-1]-'a',str[0]-'a'); if(f==1){ addedge(str[0]-'a',str[len-1]-'a',1); } } printf("Case %d:",ii); for(i=0;i<26;i++){ if(vis[i]){ for(j=i+1;j<26;j++){ if(vis[j]){ if(find(i)!=find(j)){ flag=0; break; } } } break; } } int v1=-1,v2=-1,tmp=0; for(i=0;i<26;i++){ if(!vis[i])continue; if((in[i]-out[i])%2==1){ v1=i; tmp++; } if((in[i]-out[i])%2==-1){ v2=i; tmp++; } } if(tmp==0||(tmp==2&&v1!=-1&&v2!=-1)){ if(tmp==2){ addedge(v1,v2,1); in[v2]++; out[v1]++; } } else{ flag=0; } if(!flag){ printf(" Poor boy!\n"); continue; } sum=0; for(i=0;i<26;i++){ if(!vis[i])continue; tmp=(out[i]-in[i])/2; if(tmp<0){ addedge(i,t,-tmp); } else if(tmp>0){ sum+=tmp; addedge(s,i,tmp); } } if(dinic(s,t)!=sum){ printf(" Poor boy!\n"); } else{ printf(" Well done!\n"); } } return 0; }
发表评论
-
[kruskal]hdoj 4786
2014-10-29 20:38 705大致题意: 一个无向图中,每条边都是白边或 ... -
[prim]aizuoj:There is No Alternative
2014-10-20 01:02 889题目地址:http://judge.u-aizu.ac.j ... -
[最大流唯一性判断]hdoj 4888
2014-10-18 16:14 1366题意 给出一个矩阵n行每一行数字的和,m列每列数字的 ... -
[双连通分量+队列优化dijkstra]acdream 1415
2014-10-16 04:03 1146题意: 给出一个n个点,m条边无向图(2 ≤ ... -
[2-sat]hdoj 4751
2014-10-10 21:06 819大致题意 给出一个有向图,问这个图是否能分为两个完全图 ... -
[费用流]hdoj 5045
2014-09-28 00:11 874读题的时候漏掉了“题目是按照顺序出现的”,导致网络赛中这道题 ... -
[dfs+bfs]zoj 3811
2014-09-21 09:59 989题意: 在一个无向图中,能否按照一定的顺序访问图 ... -
[二分+最大流]zoj 3691:flower
2013-04-01 21:05 1683大致题意: 在一个三维空间中有n个点,每个点的坐标 ... -
[spfa]hdoj 4460:Friend Chains
2012-11-08 21:15 1700大致题意: 一个无向图n个点,m条边,求任意两个点之 ... -
[二分匹配]zoj 3156:Taxi
2012-10-25 19:28 1187大致题意: 有n个人和m辆车(n<=m)。给出所有 ... -
[Tarjan]uva 4846:Mines
2012-10-19 10:07 1323大致题意: 给出n个地雷,每颗地雷有一个爆炸范围,这 ... -
[2-sat][位运算]zoj 3656:Bit Magic
2012-10-15 09:17 2059大致题意: 给出下面一段代码 很明显这段代码是 ... -
[二分匹配]zoj 3646:Matrix Transformer
2012-10-10 21:15 1067大致题意: 给出一个n*n的矩阵,每个矩阵元素的U或者 ... -
[拆点+网络流]2012 acm/icpc成都网络赛 hdoj 4292:Food
2012-09-16 17:15 2344大致题意: 有F种食物和D种饮料,每种食物或饮料只能 ... -
[网络流]2012 acm/icpc成都网络赛hdoj 4288:Control
2012-09-16 17:03 1361大致题意: 给出一个又n个点,m条边组成的无向图。给出两 ... -
[floyd+Tarjan]zoj 3232:It's not Floyd Algorithm
2012-09-09 09:49 1152大致题意: 给出一个有向图的传递闭包矩阵,求出这个图 ... -
[最大流]zoj 3642:Just Another Information Sharing Problem
2012-08-28 13:26 1149大致题意: 有n个人,每个人知道ai个消息,并且会 ... -
[Tarjan变形]zoj 3630:Information
2012-08-15 16:42 1162大致题意: 给出一个有向图,现在要删去一个点使得剩下的图 ... -
[Tarjan强连通分量]hdoj 3836:Equivalent Sets
2012-07-21 09:40 971大致题意: 就是给出一个有向图,求最少加多少条边可以 ... -
[最大流]zoj 3305:Get Sauce
2012-06-19 10:04 979大致题意: 有n种原材料,每种一件。现在给出m个组合 ...
相关推荐
欧拉回路的Fleury算法 欧拉回路的Fleury算法是图论中...欧拉回路的Fleury算法是一种有效的算法,可以快速判断图是否存在欧拉回路,并可以输出其中一条欧拉回路。该算法广泛应用于图论、计算机网络、交通网络等领域。
这里以构建一个度全部相同的欧拉回路,并输出欧拉回路的路径 1.构建欧拉回路 连通主要是靠树来保证,首先建立一个度为k的完全图,其中会有很多需要主要的地方 (1)首先构造树 =>保证顶点连通 (2)将度的点...
欧拉回路C++程序 随机输入任意点数,给出图中存在的欧拉回路
这段代码提供了一个完整的解决方案,用于检测和输出欧拉回路,涵盖了图的构建、性质验证、并查集操作以及欧拉回路的经典算法。它不仅展示了数据结构的应用,如邻接表和并查集,还深入讲解了图论中的一个重要概念——...
而欧拉回路则是在图中从一个顶点出发,经过每条边恰好一次,并最终返回到起点的路径。如果一个图存在欧拉回路,那么我们说这个图是欧拉图。 题目所提到的是针对有向图的欧拉回路的判断。在有向图中,边的方向决定了...
根据提供的文件信息,本文将对“欧拉回路程序java”进行详细解析,涉及的知识点主要包括:欧拉路径与欧拉回路的概念、Java程序设计基础、数据结构(如图和节点)、算法实现(欧拉回路算法)等。 ### 欧拉路径与欧拉...
通过递归的方式遍历图的每个顶点,尝试删除每条边并继续搜索,直至找到欧拉回路。 - **BFS (广度优先搜索)**:用于检查图是否连通。通过广度优先搜索,标记访问过的顶点,确保图是连通的。 #### 三、代码解析 - **...
- **题目描述**:构建特定类型的图——德布鲁因图,并找出其欧拉回路。 - **解题思路**:构建德布鲁因图后,判断其是否存在欧拉回路。 - **数据结构**:邻接表。 5. **【HDU】1956 Sightseeing tour 混合欧拉** ...
在本文中,我们将了解如何构建欧拉回路,掌握用构造证明法证明定理2的充分条件,并采用定理2的方法编程给出三个图的欧拉回路。 欧拉回路的定义 欧拉回路(Eulerian Circuit)是一种图论中的概念,它是指在一个连通...
例如,可以设计问题让参赛者找出一个图的欧拉回路,或者判断一个给定的图是否包含欧拉回路。解决这些问题通常需要运用图的遍历算法,如深度优先搜索(DFS)或广度优先搜索(BFS),并通过调整路径来确保每条边都被恰当地...
欧拉回路是图论中的一个重要概念,它在计算机科学,特别是网络流、最短路径算法以及各种优化问题中有着广泛的应用。欧拉回路是指一个图中的简单路径,起点和终点相同,并且通过每条边恰好一次。简单来说,就是从图中...
自己用C写的无向图找欧拉回路的一个例子。主要用于数据结构的学习
欧拉回路是图论中的一个重要概念,它指的是在无向图或有向图中,一个从某点出发,经过图中每条边恰好一次,最后又回到起点的路径。在学习数据结构的过程中,理解并实现欧拉回路的算法是一项基础而关键的任务。这个...
Euler_difference.txt+前向欧拉法+后向欧拉法+中心差分法+matlab程序
本资源主要内容为有向图的无向图的欧拉回路的判定,使用的编程语言为JAVA,并采用邻接表作为图的存储结构,使用并查集判断图是否连通,利用图的遍历算法得到一条有效的欧拉回路,最后通过界面将欧拉路径动态显示在...
本文主要涉及图论中的一个经典问题——欧拉路径与欧拉回路的判定及其寻找算法,并着重介绍如何利用邻接矩阵来实现这一过程。 ### 欧拉路径与欧拉回路 在图论中,欧拉路径是指一条通过图中每条边恰好一次的路径,而...
哈密尔顿回路关注的是在图中找到一个经过每个顶点恰好一次的路径,但它并不关心边的使用次数,而欧拉回路则强调每条边恰好被使用一次。 **四、寻找欧拉路径的方法** 1. **弗雷乌斯定理**:如果一个无向图包含两个...
一个欧拉图是指一个无向图,其中每个边恰好被通过一次的路径,即从任一顶点出发,沿着边行走,最后能回到起点,且所有边都被走过一次,这样的路径被称为欧拉回路。如果一个图包含这样的路径,那么该图就被称为欧拉图...
所谓欧拉回路,是一种在图中特定的路径,它从任意顶点出发,经过每条边恰好一次,并最终回到起点形成闭合回路。在计算机科学的应用中,欧拉回路涉及到多个领域,比如网络通信、数据结构优化、游戏开发中的路径规划等...