infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
http://acm.pku.edu.cn/JudgeOnline/problem?id=1364
先贴个代码,差分约束,虽然参照别人放入代码过了,但是自己也搞得不是太明白!
慢慢学习!

Source Code

Problem: 1364
User: lovecanon
Memory: 208K
Time: 0MS
Language: C++
Result: Accepted

#include<iostream>
#include
<string.h>
using namespace std;
struct node{
    
int u,v,val;
}edge[
101];
int a,b,va,i,j,n,m,dist[101];
char rel[3];
void bellman_ford(){
    memset(dist,
0,sizeof(dist));
    
int flag;
    
for(i=0;i<=n;i++){
        flag
=0;
        
for(j=1;j<=m;j++){
            
if(dist[edge[j].u]+edge[j].val<dist[edge[j].v]){//can de updated
                dist[edge[j].v]=dist[edge[j].u]+edge[j].val;
                flag
=1;
            }
        }
        
if(!flag) break;
    }
    
if(!flag) printf("lamentable kingdom\n");
    
else printf("successful conspiracy\n");
    
}
int main(){
    
while(scanf("%d",&n)&&n){
        scanf(
"%d",&m);
        
for(i=1;i<=m;i++){
            scanf(
"%d%d%s%d",&a,&b,rel,&va);
            
if(rel[0]=='l'){
                edge[i].u
=a+b;
                edge[i].v
=a-1;//a-1 not b-1 在这儿错了好多次
                edge[i].val=va-1;
            }
            
else{
                edge[i].u
=a-1;
                edge[i].v
=a+b;
                edge[i].val
=-1-va;
            }
        }
        bellman_ford();
    }
    
return 0;
}



posted on 2008-11-02 22:00 infinity 阅读(717) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理