首页 > 代码库 > poj 2240 Bellman-Flod 求环
poj 2240 Bellman-Flod 求环
http://poj.org/problem?id=2240
深刻体现了自己代码能力有问题外加改模板能力有问题,外加Debug有问题。以后做到:
1、算法原理可以轻易弄出来,
2、代码模板自己收集各种用法,以及已经的做过的改变的方法;
3、没有完整清晰的思路不敲代码;
4、在Debug时没有基本绝对的把握,不点击“编译+运行”,不乱试
回到这道题:
我主要是想把Bellman-Ford的模板改为链式前向星的,然后就各种悲剧调试......
学到三点:1、比例的初始化,求最大,源1.0,尚不可到达0,
2、Bellman-Ford求环,可以将原来的n-1次循环(就是最多经过n-1条边时最短路径),改为n次循环,当然也可以再把判负权的代码改了,相当于第n次。 这就是我下面贴的两个版本的代码:
3、链式前向星的Bellman-Ford模板如下
两种版本都是125ms AC--其实一样
n次循环:
#include<cstdio> #include<cstring> #include <string> #include <map> #include <iostream> using namespace std; //#define INF 0x0f0f0f0f const double INF = 0; #define MAXN 1011 #define Max(a,b) (a)>(b)?(a):(b) struct Node{ int to; double w; int next; }edge[MAXN]; int head[MAXN],s,n,m,path[MAXN]; double dist[MAXN];//注意w以及该数组的类型 using namespace std; void init() { memset(head,-1,sizeof(head)); memset(path,-1,sizeof(path)); } void addEdge(int u,int v,double w,int k) { edge[k].to=v; edge[k].w=w; edge[k].next=head[u]; head[u]=k;/*起点为u的边为edge[k]*/ } int Bellman_Ford(int v0)//v0--soure { for(int i=0;i<n;i++)dist[i]=0;//1.0; dist[v0]=1.0; for(int i=0;i<n;i++) for(int u=0;u<n;u++) { for(int j=head[u];j!=-1;j=edge[j].next) { if(dist[u]*edge[j].w>dist[edge[j].to]) { dist[edge[j].to]= dist[u]*edge[j].w; path[edge[j].to]=u; } } } if(dist[v0]>1.0)return 1; return 0; } int main() { // freopen("poj2240.txt","r",stdin); int icase=0,flag; double w; string u,v; string str; while(scanf("%d",&n) && n) { init(); map<string, int>ss; for(int i=0;i<n;i++) { cin>>str; ss[str]=i; } scanf("%d",&m); for(int i=0;i<m;i++) { cin >> u >> w >> v; addEdge(ss[u],ss[v],w,i); } flag=1; for(int i=0;i<n;i++) { if(Bellman_Ford(i)){flag=0;printf("Case %d: Yes\n",++icase);break;} } if(flag) printf("Case %d: No\n",++icase); } return 0; }
改负权代码 可以作为链式前向星的Bellman-Ford的模板:
#include<cstdio> #include<cstring> #include <string> #include <map> #include <iostream> using namespace std; //#define INF 0x0f0f0f0f const double INF = 0; #define MAXN 1011 #define Max(a,b) (a)>(b)?(a):(b) struct Node{ int to; double w; int next; }edge[MAXN]; int head[MAXN],s,n,m,path[MAXN]; double dist[MAXN];//注意w以及该数组的类型 using namespace std; void init() { memset(head,-1,sizeof(head)); memset(path,-1,sizeof(path)); } void addEdge(int u,int v,double w,int k) { edge[k].to=v; edge[k].w=w; edge[k].next=head[u]; head[u]=k;/*起点为u的边为edge[k]*/ } int Bellman_Ford(int v0)//v0--soure { for(int i=0;i<n;i++)dist[i]=0;//1.0; dist[v0]=1; int i,j,l,u,k; for(int i=1;i<n;i++) for(u=0;u<n;u++) { for(j=head[u];j!=-1;j=edge[j].next) { if(dist[u]*edge[j].w>dist[edge[j].to]) { dist[edge[j].to]= dist[u]*edge[j].w; path[edge[j].to]=u; } } } for(int j=0;j<n;j++) { for(k=head[j];k!=-1;k=edge[k].next) { if(edge[k].to == v0 && dist[j]*edge[k].w>1.0)//dist[edge[k].to]) return 1; } } return 0; } int main() { //freopen("poj2240.txt","r",stdin); int icase=0,flag; double w; string u,v; string str; while(scanf("%d",&n) && n) { init(); map<string, int>ss; for(int i=0;i<n;i++) { cin>>str; ss[str]=i; } scanf("%d",&m); for(int i=0;i<m;i++) { cin >> u >> w >> v; addEdge(ss[u],ss[v],w,i); } flag=1; for(int i=0;i<n;i++) { if(Bellman_Ford(i)){flag=0;printf("Case %d: Yes\n",++icase);break;} } if(flag) printf("Case %d: No\n",++icase); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。