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;
}
这题比较特殊，不要求找到所有最短路径，因此判断终止方法也不太一样，见程序。
#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; //保存活动结点
for( int 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];
for( int 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;
for( int 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
古月残辉 阅读(1440)
评论(0) 编辑 收藏 引用 所属分类:
POJ