随笔-20  评论-16  文章-36  trackbacks-0
1364 King
A的第一题Bellman-Ford,这个模板挺常用,我程序中省去了父结点的构造。

#include <iostream>
#define INF 1000000
int t, n, m, i, j, k, d[110];
struct Edge{
    
int u, v, w;
}
edge[210];
bool Bellman_Ford( int s ){
    
for( i= 0; i<= n; i++ )
        d[i]
= INF;
    d[s]
= 0;
    
for( k= 1; k<= n; k++ )
        
for( i= 1; i<=m; i++ )
            
if( d[edge[i].v]> d[edge[i].u]+edge[i].w )
                d[edge[i].v]
= d[edge[i].u]+edge[i].w;
    
for( i= 1; i<= m; i++ )
        
if( d[edge[i].v]> d[edge[i].u]+edge[i].w )
            
return false;
    
return true;
}

int main(){
    
char s[3];
    
while( scanf("%d",&n) && n ){
        scanf(
"%d",&m);
        memset(d,
0,sizeof(d));
        m
+= n;
        
for( t= 1; t<= n; t++ ){
            edge[t].u
= 0;
            edge[t].v
= i;
            edge[t].w
= 0;
        }

        
for( ; t<= m; t++ ){
            scanf(
"%d%d%s%d",&i,&j,s,&k);
            
if( s[0]=='g' ){
                edge[t].u
= i+j+1;
                edge[t].v
= i;
                edge[t].w
= -k-1;
            }

            
else{
                edge[t].u
= i;
                edge[t].v
= i+j+1;
                edge[t].w
= k-1;
            }

        }

        
if( Bellman_Ford( 0 ) )
            puts(
"lamentable kingdom");
        
else
            puts(
"successful conspiracy");
    }

    
return 0;
}

1860 Currency Exchange
这题比较特殊,不要求找到所有最短路径,因此判断终止方法也不太一样,见程序。
#include <iostream>
int n, m, i, j, k, s;
double d[110], org, tmp;
struct Edge{
    
int u, v;
    
double c, r;
}
edge[310];
bool Bellman_Ford(){
    memset(d,
0,sizeof(d));
    d[s]
= org;
    
bool flg;
    
while( d[s]<= org ){
        flg
= true;
        
for( i= 1; i<=m; i++ ){
            tmp
= (d[edge[i].u]-edge[i].c)*edge[i].r;
            
if( d[edge[i].v]< tmp ){
                d[edge[i].v]
= tmp;
                flg
= false;
            }

        }

        
if( flg ) return d[s]> org;
    }

    
return true;
}

int main(){
    
double r1, r2, c1, c2;
    scanf(
"%d%d%d%lf",&n,&m,&s,&org);
    m
*= 2;
    memset(d,
0,sizeof(d));
    
for( k= 1; k<= m; k++ ){
        scanf(
"%d%d%lf%lf%lf%lf",&i,&j,&r1,&c1,&r2,&c2);
        edge[k].u
= i;
        edge[k].v
= j;
        edge[k].c
= c1;
        edge[k
++].r= r1;
        edge[k].u
= j;
        edge[k].v
= i;
        edge[k].c
= c2;
        edge[k].r
= r2;
    }

    
if( Bellman_Ford() )
        puts(
"YES");
    
else
        puts(
"NO");
    
return 0;
}

3159 Candies
这题数据比较大,用普通的Bellman-Ford方法会超时,因此用SPFA。
#include <iostream>
using namespace std;
#define INF 1000000
#define MAXN 30000
#define MAXM 150000

int N,M;    //实际的顶点数和边数
struct Edge{
    
int to, cost;
    Edge
* next;
}
edges[MAXM+1];        //MAXM为最大边数
Edge* linklist[MAXN+1]={0};        //MAXN为最大顶点数
void SPFA( Edge* linklist[], int dist[], int source ){    //参数分别为边的临接表、距离、源点,堆栈实现
    bool bInQ[MAXN+1]={0};        //判断点是否在堆栈中
    int stack[MAXN+1]={0}, top=0;    //保存活动结点
    forint i= 1; i<= N; i++ )
        dist[i]
= INF;
    dist[source]
= 0;
    stack[top
++]= source;
    
while( top ){
        
int cur= stack[--top];
        Edge
* q= linklist[cur];
        bInQ[cur]
= 0;
        
while( q ){
            
if( dist[q->to]> dist[cur]+q->cost ){
                dist[q
->to]= dist[cur]+q->cost;
                
if!bInQ[q->to] )
                    stack[top
++]= q->to;
                bInQ[q
->to]=1;
            }

            q
=q->next;
        }

    }

}

int main(){
    scanf(
"%d%d",&N,&M);
    
int m= 0, dist[MAXN+1];
    
forint i=1; i<= M; i++ ){
        
int s, e, c;
        scanf(
"%d%d%d",&s,&e,&c);
        edges[m].next
= linklist[s];
        edges[m].to
= e;
        edges[m].cost
= c;
        linklist[s]
=&edges[m++];
    }

    SPFA(linklist,dist,
1);
    printf(
"%d\n",dist[N]);
    
return 0;
}


1201 Intervals
这道题的差分约束方程是Si-Sj>=wk,因为要求的是最小值,对应的是最长路的问题,因此把SPFA稍加修改即可。
#include <iostream>
#define MAXM 50000
#define MAXN 50000
#define INF -100000
int N, M, dist[MAXN+1];
struct Edge{
    
int to, cost;
    Edge
* next;
}
edges[MAXM+2*MAXN];
Edge
* linklist[MAXN+1]={0};
void SPFA( Edge* linklist[], int source ){
    
bool bInQ[MAXN+1]={0};
    
int stack[MAXN+1]={0}, top=0;
    
forint i= 1; i<= N; i++ )
        dist[i]
= INF;
    dist[source]
= 0;
    stack[top
++]= source;
    
while( top ){
        
int cur= stack[--top];
        Edge
* q= linklist[cur];
        bInQ[cur]
= 0;
        
while( q ){
            
if( dist[q->to]< dist[cur]+q->cost ){
                dist[q
->to]= dist[cur]+q->cost;
                
if!bInQ[q->to] )
                    stack[top
++]= q->to;
                bInQ[q
->to]=1;
            }

            q
=q->next;
        }

    }

}

int main(){
    
int i, s, e, c, m= 0;
    scanf(
"%d",&M);
    
for( i=1; i<= M; i++ ){
        scanf(
"%d%d%d",&s,&e,&c);
        edges[m].next
= linklist[s];
        edges[m].to
= e+1;
        edges[m].cost
= c;
        linklist[s]
=&edges[m++];
        
if( N<= e )    N= e+1;
    }

    
for( i= 1; i< N; i++ ){
        edges[m].next
= linklist[i];
        edges[m].to
= i+1;
        edges[m].cost
= 0;
        linklist[i]
=&edges[m++];
        edges[m].next
= linklist[i+1];
        edges[m].to
= i;
        edges[m].cost
= -1;
        linklist[i
+1]=&edges[m++];
    }

    M
= m-1;
    SPFA(linklist,
1);
    printf(
"%d\n",dist[N]);
    
return 0;
}

posted on 2009-04-23 18:17 古月残辉 阅读(1471) 评论(0)  编辑 收藏 引用 所属分类: POJ

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