第一部分 Dijkstra 算法
POJ 2387 ——Til the Cows Come Home
最典型的最短路题目，求两点间的最短路径，一次Dij即可，代码如下:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX_INTEGER 0x7fffffff
int n;
int const MAX=2000;
int value[MAX][MAX];
bool visit[MAX];
int dis[MAX];
int dijkstra()
{
memset(visit,false,sizeof(visit));
int i;
int j;
for(i=1;i<=n;i++)
{
dis[i]=value[n][i];
visit[i]=false;
}
value[n][n]=0;
dis[n]=0;visit[n]=true;
for(i=1;i<n;i++)
{
int mark_num=n;
int mark_dis=MAX_INTEGER;
int temp=MAX_INTEGER;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<temp)
{
mark_num=j;
temp=dis[j];
}
}
visit[mark_num]=true;
for(j=1;j<=n;j++)
{
if((!visit[j])&&(value[mark_num][j]<MAX_INTEGER))
{
int newdis=dis[mark_num]+value[mark_num][j];
if(newdis<dis[j])
{
dis[j]=newdis;
}
}
}
}
return dis[1];
}
int main ()
{
int t;
int i,j;
while( scanf("%d%d",&t,&n)!=EOF)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
value[i][j]=MAX_INTEGER;
}
for(i=1;i<=t;i++)
{
int a,b,len;
scanf("%d%d%d",&a,&b,&len);
if(len<value[a][b])
{
value[a][b]=len;
value[b][a]=len;
}
}
cout<<dijkstra()<<endl;
}
return 0;
}
POJ 2253——Frogger
Dij的变形，这道题目的意思大致是，给你起点和终点，还有一些可用来中间过度的点，首先保证你能够跳跃到终点，同时还要保证你的跳跃跨度最小，也就是从起点到终点路径上的最大的那条边要尽量小，这个有点绕，所以我把这道题目改一下^_^：
等价题：假设你在玩一个闯关游戏，目的是到达终点闯关，走哪条路无关紧要，你把那些点之间的路径看成是怪物，路径长度看成是怪物的能量值，如果你想击败怪物顺利闯关的话，你的能量值必须高于怪物的能量值，当然获得能量值是需要付出代价的，现在你想用最少的代价通关，求这个最小的能量值是多少？
不难想到，此题可以用Dij来解，只需要把sum改成max即可。不得不提的是，这里不是求最短路径，而是求连通图的最小边的问题，它们都可以用Dij，个人感觉它们似乎是平行的关系，只不过是Dij大环境下的2个变种罢了。在最短路径问题中，dis[i]数组中存储的是，i点到原点的最小距离，而在连通图最小边问题中，dis[i]数组中存储的是i点到周围任何一个点的最小距离(当然这个距离是通过不断的松弛，最后才得到的^_^)
代码如下：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX_NUMBER 0x7fffffff
double len(int a,int b,int c,int d)
{
return sqrt((double)((a-c)*(a-c)+(d-b)*(d-b)));
}
struct dot
{
int x;
int y;
}dotset[201];
int n;
int const MAX=201;
double record[MAX];
double value[MAX][MAX];
bool visit[MAX];
double dis[MAX];
double dijkstra()
{
double max_step=0;
memset(visit,false,sizeof(visit));
int i;
int j;
for(i=1;i<=n;i++)
{
dis[i]=value[1][i];
visit[i]=false;
}
dis[1]=0;visit[1]=true;
for(i=1;i<n;i++)
{
int mark_num=1;
double temp=MAX_NUMBER;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<temp)
{
mark_num=j;
temp=dis[j];
}
}
if(temp>max_step)
max_step=temp;
if(mark_num==2)
return max_step;
visit[mark_num]=true;
for(j=1;j<=n;j++)
{
if((!visit[j]))
{
double newdis=value[mark_num][j];
if(newdis<dis[j])
{
dis[j]=newdis;
}
}
}
}
}
int main ()
{
int i,j,k;
for(k=1;;k++)
{
scanf("%d",&n);
if(n==0)
break;
for(i=1;i<=n;i++)
{
scanf("%d %d",&dotset[i].x,&dotset[i].y);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
value[i][j]=len(dotset[i].x,dotset[i].y,dotset[j].x,dotset[j].y);
}
}
printf("Scenario #%d\nFrog Distance = %.3f\n\n",k,dijkstra());
}
return 0;
}
POJ 1797——Heavy Transportation
还是最短路，与frogger正好相反，求的是连通图最小边的问题，可以与上一题对应起来看。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 1001
#define MIN_NUMBER 0
int n;
int value[MAX][MAX];
bool visit[MAX];
int dis[MAX];
int dijkstra()
{
int max_weight=1000001;
memset(visit,false,sizeof(visit));
int i;
int j;
for(i=1;i<=n;i++)
{
value[i][i]=0;
dis[i]=value[1][i];
visit[i]=false;
}
dis[1]=0;visit[1]=true;
for(i=1;i<n;i++)
{
int mark_num=1;
int temp=MIN_NUMBER;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]>temp)
{
mark_num=j;
temp=dis[j];
}
}
if(temp<max_weight)
max_weight=temp;
if(mark_num==n)
return max_weight;
visit[mark_num]=true;
for(j=1;j<=n;j++)
{
if((!visit[j])&&value[mark_num][j]!=MIN_NUMBER)
{
int newdis=value[mark_num][j];
if(newdis>dis[j])
{
dis[j]=newdis;
}
}
}
}
}
int main ()
{
int i,j,k;
int m;
int testcase;
scanf("%d",&testcase);
for(k=1;k<=testcase;k++)
{
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
value[i][j]=MIN_NUMBER;
}
}
for(i=1;i<=m;i++)
{
int a,b,len;
scanf("%d %d %d",&a,&b,&len);
if(len>value[a][b])
{
value[a][b]=len;
value[b][a]=len;
}
}
printf("Scenario #%d:\n%d\n\n",k,dijkstra());
}
return 0;
}
POJ 3268——
Silver Cow Party
正反两次使用Dijkstra算法即可
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 1005
#define MAX_NUM 0x7fffffff
int n;
int valuecome[MAX][MAX];
int valueback[MAX][MAX];
int dis[MAX];
bool visit[MAX];
int record[MAX];
void dijkstra(int x)
{
int temp=MAX_NUM;
int i;
int j;
int mark;
memset(visit,false,sizeof(visit));
for(i=1;i<=n;i++)
{
valuecome[i][i]=0;
dis[i]=valuecome[x][i];
}
dis[x]=0;
visit[x]=true;
for(i=1;i<n;i++)
{
temp=MAX_NUM;
mark=x;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<temp)
{
temp=dis[j];
mark=j;
}
}
visit[mark]=true;
for(j=1;j<=n;j++)
{
if((!visit[j])&&(valuecome[mark][j]<MAX_NUM))
{
int newdis=dis[mark]+valuecome[mark][j];
if(newdis<dis[j])
{
dis[j]=newdis;
}
}
}
}
}
void dijkstra2(int x)
{
int temp=MAX_NUM;
int i;
int j;
int mark;
memset(visit,false,sizeof(visit));
for(i=1;i<=n;i++)
{
valueback[i][i]=0;
dis[i]=valueback[x][i];
}
dis[x]=0;
visit[x]=true;
for(i=1;i<n;i++)
{
temp=MAX_NUM;
mark=x;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<temp)
{
temp=dis[j];
mark=j;
}
}
visit[mark]=true;
for(j=1;j<=n;j++)
{
if((!visit[j])&&(valueback[mark][j]<MAX_NUM))
{
int newdis=dis[mark]+valueback[mark][j];
if(newdis<dis[j])
{
dis[j]=newdis;
}
}
}
}
}
int main ()
{
int m,x;
int i,j;
int u,v,len;
scanf("%d%d%d",&n,&m,&x);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
valuecome[i][j]=MAX_NUM;
valueback[i][j]=MAX_NUM;
}
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&len);
if(len<valuecome[u][v])
{
valuecome[u][v]=len;
valueback[v][u]=len;
}
}
dijkstra(x);
for(i=1;i<=n;i++)
{
record[i]+=dis[i];
}
dijkstra2(x);
for(i=1;i<=n;i++)
{
record[i]+=dis[i];
}
int max=0;
max=0;
for(i=1;i<=n;i++)
{
if(record[i]>max&&i!=x)
max=record[i];
}
printf("%d\n",max);
return 0;
}
第二部分 Bellman-Ford算法
POJ 1860——Currency Exchange
Bellman_Ford的经典变形。。。精度很重要
#include<stdio.h>
#include<memory.h>
struct node
{
int u,v;
double r,c;
};
int n,m,s;
double val;
node edge[1001];
int eg;
bool bellman()
{
double dist[102];
memset(dist,0,sizeof(dist));
int i;
int k;
int flag = 0;
dist[s] = val;
while(dist[s]<=val)
{
flag = 0;
for(i = 0;i<=eg;i++)
{
if(dist[edge[i].v]<(dist[edge[i].u]-edge[i].c)*edge[i].r)
{
dist[edge[i].v] = (dist[edge[i].u]-edge[i].c)*edge[i].r;
flag=1;
}
}
if(!flag)
return dist[s]>val;
}
return true;
}
int main()
{
int i;
int a,b;
double rab, cab, rba ,cba;
while(scanf("%d %d %d %lf",&n,&m,&s,&val)!=EOF)
{
eg = 0;
for(i = 0;i<m;i++)
{
scanf("%d %d %lf %lf %lf %lf",&a,&b,&rab,&cab,&rba,&cba);
edge[eg].u = a;
edge[eg].v = b;
edge[eg].r = rab;
edge[eg].c = cab;
eg++;
edge[eg].u = b;
edge[eg].v = a;
edge[eg].r = rba;
edge[eg].c = cba;
eg++;
}
if(bellman())
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
POJ 3259——Wormholes（寻找负权回路）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3259
题意 ： 一个famer有一些农场，这些农场里面有一些田地，田地里面有一些虫洞，田地和田地之间有路，虫洞有这样的性质： 时间倒流。问你这个农民能不能看到他自己，也就是说，有没有这样一条路径，能利用虫洞的时间倒流的性质，让这个人能在这个点出发前回去，这样他就是能看到他自己
通常情况下图中的边权都为正数，这个时候可以用Dij算法，但有的时候图中的边权会为负值，这时候Dij算法便失去它的作用了，此时可以用Bellman算法，值得一提的是我们通常不用bellman算法来求最短路径，寻找负权回路才是Bellman算法最主要的应用领域（负权回路是指边权之和为负数的环）
这道题目的大意是让你判断给出的图中是不是有负权回路。此时Bellman便大显神威了:-)
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 501
#define MAX_NUM 10001
struct node
{
int u;
int v;
int w;
}edge[5500];
int n;
int m;
int w;
int dis[MAX];
bool bellman ()
{
int i,j;
for(i=1;i<=n;i++)
{
dis[i]=MAX_NUM;
}
dis[1]=0;
for(i=1;i<=n-1;i++)
{
for(j=1;j<=2*m+w;j++)
{
if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w)
dis[edge[j].v]=dis[edge[j].u]+edge[j].w;
}
}
for(i=1;i<=2*m+w;i++)
{
if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
return false;
}
return true;
}
int main ()
{
int testcase;
scanf("%d",&testcase);
int pos=0;
int i,j,k;
for(i=1;i<=testcase;i++)
{
pos=0;
scanf("%d%d%d",&n,&m,&w);
for(j=1;j<=m;j++)
{
pos++;
scanf("%d%d%d",&edge[pos].u,&edge[pos].v,&edge[pos].w);
pos++;
edge[pos].v=edge[pos-1].u;
edge[pos].u=edge[pos-1].v;
edge[pos].w=edge[pos-1].w;
}
for(j=1;j<=w;j++)
{
pos++;
scanf("%d%d%d",&edge[pos].u,&edge[pos].v,&edge[pos].w);
edge[pos].w=-edge[pos].w;
}
if(bellman())
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
第三部分 Floyd 算法
POJ 1502——MPI Maelstrom
就是要求出源点到其他各点的最短路，然后在求出最大值，由于点的数目很小，可以直接使用floyd，代码十分简洁。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxint 1000000000
int value[101][101];
char test[100];
bool isdigit(char test[])
{
if(test[0]!='x')
return true;
else
return false;
}
int main ()
{
int temp;
int i,j,k;
int n;
while(cin>>n)
{
for(i=1;i<=n;i++)
value[i][i]=0;
for(i=2;i<=n;i++)
{
for(j=1;j<=i-1;j++)
{
cin>>test;
if(isdigit(test))
{
sscanf(test,"%d",&temp);
value[i][j]=temp;
value[j][i]=temp;
}
else
{
value[i][j]=maxint;
value[j][i]=maxint;
}
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(value[i][k]!=maxint&&value[k][j]!=maxint)
{
if(value[i][k]+value[k][j]<value[i][j])
value[i][j]=value[i][k]+value[k][j];
}
}
}
}
int max=0;
for(i=2;i<=n;i++)
{
if(value[1][i]>max)
max=value[i][1];
}
cout<<max<<endl;
}
return 0;
}
POJ 3660——传递闭包
这道题是一道关于floyd的图论题。题目的意思是说有n头牛比赛，m种比赛结果，最后问你一共有多少头牛的排名被确定了，其中如果a战胜b，b战胜c，则也可以说a战胜c，即可以传递胜负。这样如果一头牛的被x头牛打败，打败y头牛，且x+y=n-1，则我们容易知道这头牛的排名就被确定了，所以我们只要将任何两头牛的胜负关系确定了，在遍历所有牛判断一下是否满足x+y=n-1，将满足这个条件的牛数目加起来就是所求解。
#include<iostream>
#include<cmath>
using namespace std;
int map[101][101]={0};
int main ()
{
int n,m;
scanf("%d %d",&n,&m);
int i,j,k;
for(i=1;i<=m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
map[a][b]=1;
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(map[i][k]==1&&map[k][j]==1)
map[i][j]=1;
}
}
}
int ans=0;
int temp=0;
for(i=1;i<=n;i++)
{
temp=0;
for(j=1;j<=n;j++)
{
if(j==i)
continue;
else if(map[i][j]==1||map[j][i]==1)
temp++;
}
if(temp==n-1)
ans++;
}
cout<<ans<<endl;
return 0;
}
POJ 2240——Arbitrage
这就是个套汇的问题，可以用Floyd求最大环，然后判断是不是大于1。
#include <cstdio>
#include <string>
#include <map>
using namespace std;
map<string,int> MAP;
double value[31][31];
double rate;
double tempfloat;
int main()
{
int i,j,k,n,m;
int count=1;
char temp[100],temp1[100];
while(scanf("%d",&n))
{
if(n==0)
break;
MAP.clear();
memset(value,0,sizeof(value));
for(i=1;i<=n;i++)
{
scanf("%s",temp);
MAP[(string)temp]=i;
}
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%s %lf %s",temp,&rate,temp1);
value[MAP[(string)temp]][MAP[(string)temp1]]=rate;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
tempfloat=value[i][k]*value[k][j];
if(tempfloat>value[i][j])
value[i][j]=tempfloat;
}
for(i=1;i<=n;i++)
if(value[i][i]>1)
{
printf("Case %d: Yes\n",count++);
break;
}
if(i==n+1)
printf("Case %d: No\n",count++);
}
}
第四部分 SPFA 算法(Shortest Path Faster Algorithm)
POJ 1511——Invitation Cards
顾名思义，SPFA算法的特点就是快，这道题用之前的任何算法均会超时，只有使用SPFA算法才能AC,可见SPFA算法的优越性^_^
//Coded by abilitytao
//Time:2009-04-10 22:49:58
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
#define MAX_NUM 1000000001
#define MAX_DOTNUM 1000001
int n,m;
queue<int>myqueue;
bool mark[MAX_DOTNUM];
__int64 dis[MAX_DOTNUM];
struct node
{
int v;
int w;
node *next;
}edge[MAX_DOTNUM];//此邻接表用于存储正向图
node reversed_edge[MAX_DOTNUM];//此逆邻接表用于存储逆向图
void initial(node edge[])//邻接表的初始化，里面封装了回收上一次操作所分配之内存的操作
{
int i;
node *p;
node *q;
for(i=1;i<=n;i++)
{
p=&edge[i];
q=p->next;
while(q!=NULL)
{
p->next=q->next;
delete q;
q=p->next;
}
}
}
void input_case()//每一个case的输入函数
{
int i;
for(i=1;i<=m;i++)
{
node *p;
node *q;
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
/**//**//**/////////////////////////
p=&edge[a];
q=new node;
q->v=b;
q->w=c;
q->next=p->next;
p->next=q;
/**//**//**/////////////////////////
p=&reversed_edge[b];
q=new node;
q->v=a;
q->w=c;
q->next=p->next;
p->next=q;
}
}
void spfa(node edge[])//SPFA部分
{
int i;
/**//**//**////////////////////////////////////////////////////////////////
memset(mark,false,sizeof(mark));
for(i=1;i<=n;i++)
dis[i]=MAX_NUM;
while(myqueue.size()!=0)
myqueue.pop();
/**//**//**////////////////////////////////////////////////////////////
dis[1]=0;
mark[1]=true;
myqueue.push(1);
while(myqueue.size()!=0)//如果队列不空，则进行松弛操作，直到队列空为止
{
int temp=myqueue.front();
myqueue.pop();
mark[temp]=false;
node *p;
for(p=edge[temp].next;p!=NULL;p=p->next)
{
if(dis[p->v]>dis[temp]+p->w)
{
dis[p->v]=dis[temp]+p->w;
if(mark[p->v]!=true)
{
myqueue.push(p->v);
mark[p->v]=true;
}
}
}
}
}
int main()
{
int testcase;
int i,j;
__int64 sum;
scanf("%d",&testcase);
for(i=1;i<=MAX_DOTNUM-1;i++)
{
edge[i].v=i;
edge[i].w=0;
edge[i].next=NULL;
}
for(i=1;i<=MAX_DOTNUM-1;i++)
{
reversed_edge[i].v=i;
reversed_edge[i].w=0;
reversed_edge[i].next=NULL;
}
for(i=1;i<=testcase;i++)
{
sum=0;
scanf("%d%d",&n,&m);
initial(edge);
initial(reversed_edge);
input_case();
spfa(edge);
for(j=1;j<=n;j++)
sum+=dis[j];
spfa(reversed_edge);
for(j=1;j<=n;j++)
sum+=dis[j];
printf("%I64d\n",sum);
}
system("pause");
return 0;
}
再次看这个题目，发现以前的代码风格实在是太差了，同样的题目，现在写只要91行。。。。。。。。。。。。。。。。。。。。。。。。
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
#define bint long long
int const maxn=1000000;
int const maxm=2000000;
int const INF=1000000000;
struct node
{
int t,w;
node *next;
}edge[maxm],*adj[maxn],*nadj[maxn];
int len=0;
void init(int n){
for(int i=0;i<n;i++){adj[i]=NULL;nadj[i]=NULL;}
len=0;
}
void addedge(node *adj[],int u,int v,int w){
edge[len].t=v;edge[len].w=w;edge[len].next=adj[u];adj[u]=&edge[len++];
}
void insert(int u,int v,int w)
{
addedge(adj,u,v,w);
addedge(nadj,v,u,w);
}
int use[maxn];
bint dis[maxn];
queue<int>Q;
bint SPFA(node *adj[],int n,int s,int t)
{
while(!Q.empty())Q.pop();fill(use,use+n,0);fill(dis,dis+n,INF);
Q.push(s);use[s]=1;dis[s]=0;
while(!Q.empty())
{
int t=Q.front();Q.pop();use[t]=0;
for(node *p=adj[t];p;p=p->next){
if(dis[t]+p->w<dis[p->t]){
dis[p->t]=dis[t]+p->w;
if(!use[p->t]){
use[p->t]=1;
Q.push(p->t);
}
}
}
}
if(dis[t]==INF)return -1;
else return dis[t];
}
int main()
{
int ca;
scanf("%d",&ca);
bint sum;
while(ca--)
{
sum=0;
int n,m;
scanf("%d%d",&n,&m);
init(n);
for(int i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
insert(a-1,b-1,c);
}
SPFA(adj,n,0,n-1);
for(int i=0;i<n;i++)
sum+=dis[i];
SPFA(nadj,n,0,n-1);
for(int i=0;i<n;i++)
sum+=dis[i];
printf("%lld\n",sum);
}
return 0;
}
特别感谢 ：WinterLegend
2009年7月7日21:20:31