- 浏览: 376840 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
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 661大致题意: 一个无向图中,每条边都是白边或 ... -
[prim]aizuoj:There is No Alternative
2014-10-20 01:02 845题目地址:http://judge.u-aizu.ac.j ... -
[最大流唯一性判断]hdoj 4888
2014-10-18 16:14 1311题意 给出一个矩阵n行每一行数字的和,m列每列数字的 ... -
[双连通分量+队列优化dijkstra]acdream 1415
2014-10-16 04:03 1094题意: 给出一个n个点,m条边无向图(2 ≤ ... -
[2-sat]hdoj 4751
2014-10-10 21:06 764大致题意 给出一个有向图,问这个图是否能分为两个完全图 ... -
[费用流]hdoj 5045
2014-09-28 00:11 828读题的时候漏掉了“题目是按照顺序出现的”,导致网络赛中这道题 ... -
[dfs+bfs]zoj 3811
2014-09-21 09:59 898题意: 在一个无向图中,能否按照一定的顺序访问图 ... -
[二分+最大流]zoj 3691:flower
2013-04-01 21:05 1609大致题意: 在一个三维空间中有n个点,每个点的坐标 ... -
[spfa]hdoj 4460:Friend Chains
2012-11-08 21:15 1592大致题意: 一个无向图n个点,m条边,求任意两个点之 ... -
[二分匹配]zoj 3156:Taxi
2012-10-25 19:28 1067大致题意: 有n个人和m辆车(n<=m)。给出所有 ... -
[Tarjan]uva 4846:Mines
2012-10-19 10:07 1220大致题意: 给出n个地雷,每颗地雷有一个爆炸范围,这 ... -
[2-sat][位运算]zoj 3656:Bit Magic
2012-10-15 09:17 1915大致题意: 给出下面一段代码 很明显这段代码是 ... -
[二分匹配]zoj 3646:Matrix Transformer
2012-10-10 21:15 973大致题意: 给出一个n*n的矩阵,每个矩阵元素的U或者 ... -
[拆点+网络流]2012 acm/icpc成都网络赛 hdoj 4292:Food
2012-09-16 17:15 2214大致题意: 有F种食物和D种饮料,每种食物或饮料只能 ... -
[网络流]2012 acm/icpc成都网络赛hdoj 4288:Control
2012-09-16 17:03 1297大致题意: 给出一个又n个点,m条边组成的无向图。给出两 ... -
[floyd+Tarjan]zoj 3232:It's not Floyd Algorithm
2012-09-09 09:49 1067大致题意: 给出一个有向图的传递闭包矩阵,求出这个图 ... -
[最大流]zoj 3642:Just Another Information Sharing Problem
2012-08-28 13:26 1094大致题意: 有n个人,每个人知道ai个消息,并且会 ... -
[Tarjan变形]zoj 3630:Information
2012-08-15 16:42 1103大致题意: 给出一个有向图,现在要删去一个点使得剩下的图 ... -
[Tarjan强连通分量]hdoj 3836:Equivalent Sets
2012-07-21 09:40 919大致题意: 就是给出一个有向图,求最少加多少条边可以 ... -
[最大流]zoj 3305:Get Sauce
2012-06-19 10:04 930大致题意: 有n种原材料,每种一件。现在给出m个组合 ...
相关推荐
这里以构建一个度全部相同的欧拉回路,并输出欧拉回路的路径 1.构建欧拉回路 连通主要是靠树来保证,首先建立一个度为k的完全图,其中会有很多需要主要的地方 (1)首先构造树 =>保证顶点连通 (2)将度的点...
欧拉回路C++程序 随机输入任意点数,给出图中存在的欧拉回路
图论——欧拉回路的Fleury算法 根据离散数学教材中思想 实现求欧拉回路。
欧拉回路性质与应用探究欧拉回路性质与应用探究欧拉回路性质与应用探究
关于算法与图论中有向图的欧拉回路的判断,判断一个有向图是否有欧拉回路
自己用C写的无向图找欧拉回路的一个例子。主要用于数据结构的学习
Euler_difference.txt+前向欧拉法+后向欧拉法+中心差分法+matlab程序
本资源主要内容为有向图的无向图的欧拉回路的判定,使用的编程语言为JAVA,并采用邻接表作为图的存储结构,使用并查集判断图是否连通,利用图的遍历算法得到一条有效的欧拉回路,最后通过界面将欧拉路径动态显示在...
欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。然后通过几个实例,介绍了与欧拉回路相关的几类典型问题。最后对欧拉回路的模型进行了总结,...
有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。 一共两个子任务: 无向图。 有向图。 输入格式 第一行一个整数 t,表示子任务编号。t∈{1,2},如果 t=1 ...
实现了欧拉回路的程序实现即遍历图输出欧拉回路
找欧拉回路,本程序实现了对一个欧拉图形找其欧拉回路
对欧拉回路的实验报告,有利于大家更好地理解欧拉回路,对要实验报告的人很适合。本算法使用c语言编写的 如需其他语言请自行更改。
Catenyms poj hoj 欧拉回路输出路径
欧拉回路题集,适用于算法爱好者,内含 欧拉回路的多种题型
求图的欧拉回路的算法,有注释,c++版的,自己写的,O(n)的复杂度
有图论中的很多知识,比如图论概念,类型等,还有欧拉回路与汉密尔顿路
实验_38_如何构建欧拉回路.pdf
有无向欧拉回路(邻接阵) template 有无向欧拉回路(邻接阵) template 有无向欧拉回路(邻接阵) template 有无向欧拉回路(邻接阵) template
【摘要】欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。然后通过几个实例,介绍了与欧拉回路相关