图论算法——最短路系列-白红宇

图论算法——最短路系列

阅读量：4560 次

发布时间：2019-06-08

本文共 11214 字，大约阅读时间需要 37 分钟。

最短路经典算法整理

1.弗洛伊德：三重循环

例题：

codevs

1020 孪生蜘蛛

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述

Description

在G城保卫战中，超级孪生蜘蛛Phantom001和Phantom002作为第三层防卫被派往守护内城南端一带极为隐秘的通道。

根据防护中心的消息，敌方已经有一只特种飞蛾避过第二层防卫，直逼内城南端通道入口。但优秀的蜘蛛已经在每个通道内埋下了坚固的大网，无论飞蛾进入哪个通道，他只有死路一条！（因为他是无法挣脱超级蛛网的）

现在，001和002分别驻扎在某两个通道内。各通道通过内线相通，通过每条内线需要一定的时间。当特种飞蛾被困某处，001或002会迅速赶来把它结果掉（当然是耗时最少的那个）。

001跟002都想尽早的完成任务，他们希望选择在最坏情况下能尽早完成任务的方案。

输入描述

Input Description

第一行为一个整数N (N<=100) 表示通道数目。

接下来若干行每行三个正整数a,b,t 表示通道a,b有内线相连，通过的时间为t。(t<=100)

（输入保证每个通道都直接/间接连通）

输出描述

Output Description

两个不同的整数x1,x2，分别为001，002驻扎的地点。（如果有多解，请输出x1最小的方案，x1相同则输出x2最小的方案）

样例输入

Sample Input

1 2 5

2 3 10

3 1 3

样例输出

Sample Output

1 2

数据范围及提示 Data Size & Hint

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define inf 0x7fffffff 6 using namespace std; 7 int d[110][110],b[110][110],id; 8 int main (){ 9     int n,a,b1,t;10     cin>>n;11     for (int i=0;i<=n;i++)12       for (int j=0;j<=n;j++)13         if (i==j) d[i][j]=0;14         else d[i][j]=inf;15     while(scanf("%d%d%d",&a,&b1,&t)!=EOF)16         d[a][b1]=d[b1][a]=t;17     18     for (int k=1;k<=n;k++)19       for (int i=1;i<=n;i++)20         for (int j=1;j<=n;j++)21           if (d[i][k]
         
          
           b[i][j])Min=b[i][j],p=i,q=j;35 }36 cout<
           <<" "<

上述算法注意用弗洛伊德处理最坏情况；

2 Dijkstra

1 设起点为s，dis[v]表示从s到v的最短路径，pre[v]为v的前驱节点，用来输出路径。 2        a)初始化：dis[v]=∞(v≠s); dis[s]=0; pre[s]=0;  3        b)For (i = 1; i <= n ; i++) 4             1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的。 5             2.u标记为已确定最短路径 6             3.For 与u相连的每个未确定最短路径的顶点v 7               if  (dis[u]+w[u][v] < dis[v])  8                { 9                   dis[v] = dis[u] + w[u][v];10                   pre[v] = u;11                }12         c)算法结束：dis[v]为s到v的最短距离；pre[v]为v的前驱节点，用来输出路径。

例题：

最小花费

最小花费

【问题描述】

在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定

这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收

到100元。

【输入格式】

第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。

以下m行每行输入三个正整数x,y,z，表示标号为x的人和标号为y的人之间互相转账需要扣除z%

的手续费 (z<100)。

最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。

【输出格式】

输出A使得B到账100元最少需要的总费用。精确到小数点后8位。

【输入样例】

3 3

1 2 1

2 3 2

1 3 3

1 3

【输出样例】

103.07153164

【数据规模】

1<=n<=2000

1 #include
       
         2 using namespace std; 3 double a[2001][2001],dis[2001]= {
     0},minn; 4 int n,m,i,j,k,x,y,f[2001]= {
     0}; 5 void init() { 6     cin>>n>>m; 7     for(i=1; i<=m; i++) { 8         scanf("%d%d",&j,&k); 9         scanf("%lf",&a[j][k]);10         a[j][k]=(100-a[j][k])/100;11         a[k][j]=a[j][k];12     }13     cin>>x>>y;14 }15 void dijkstra(int x) {16     for(i=1; i<=n; i++)dis[i]=a[x][i];17     dis[x]=1;18     f[x]=1;19     for(i=1; i<=n-1; i++) {20         minn=0;21         for(j=1; j<=n; j++)22             if(f[j]==0&&dis[j]>minn) {23                 k=j;24                 minn=dis[j];25             }26         f[k]=1;27         if(k==y)break;28         for(j=1; j<=n; j++)29             if(f[j]==0&&dis[k]*a[k][j]>dis[j])dis[j]=dis[k]*a[k][j]

}31 }32 int main() {33     init();34     dijkstra(x);35     printf("%0.8lf",100/dis[y]);36     return 0;37 }

3 Bellman

此算法性能较差，不经常用；

1 设s为起点，dis[v]即为s到v的最短距离，pre[v]为v前驱。w[j]是边j的长度，且j连接u、v。2 初始化：dis[s]=0,dis[v]=∞（v≠s），pre[s]=03 For (i = 1; i <= n-1; i++)4 For (j = 1; j <= E; j++)         //注意要枚举所有边，不能枚举点。5    if (dis[u]+w[j]

不做过多介绍；

4 spfa

1   dis[i]记录从起点s到i的最短路径，w[i][j]记录连接i，j的边的长度。pre[v]记录前趋。 2     team[1..n]为队列，头指针head，尾指针tail。 3     布尔数组exist[1..n]记录一个点是否现在存在在队列中。 4     初始化：dis[s]=0,dis[v]=∞（v≠s），memset(exist,false,sizeof(exist)); 5     起点入队team[1]=s; head=0; tail=1;exist[s]=true; 6     do 7     {  8     1、头指针向下移一位，取出指向的点u。 9     2、exist[u]=false;已被取出了队列10     3、for与u相连的所有点v          //注意不要去枚举所有点，用数组模拟邻接表存储11               if (dis[v]>dis[u]+w[u][v])12                  {13                       dis[v]=dis[u]+w[u][v];14                       pre[v]=u;15                      if (!exist[v]) //队列中不存在v点，v入队。16                        {17                                     //尾指针下移一位，v入队;18                                   exist[v]=true;19                        }20                  ｝21     }22     while (head < tail);

例题；

香甜的黄油

(Sweet Butter

)

【问题描述】

农夫

John

发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道

（

1<=N<=500

）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜

黄油。当然，他将付出额外的费用在奶牛上。

农夫

John

很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他

可以在晚上挤奶。

农夫

John

知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场

（他将把糖放在那）。

【输入格式】

butter.in

第一行

三个数：奶牛数

，牧场数

（

2<=P<=800

），牧场间道路数

C(1<=C<=1450)

。

第二行到第

N+1

行

: 1

到

头奶牛所在的牧场号。

第

N+2

行到第

N+C+1

行：每行有三个数：相连的牧场

、

，两牧场间距（

1<=D<=255

），当然，连接是双向的。

【输出格式】

butter.out

一行

输出奶牛必须行走的最小的距离和

【输入样例】

3 4 5

1 2 1

1 3 5

2 3 7

2 4 3

3 4 5

样例图形

P1 @--1--@ C1

\ |\

\ | \

5 7 3

\ | \

\| \ C3

C2 @--5--@

P3 P4

【输出样例】

//说明：放在

号牧场最优

代码；

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 int n,p,c,i,j,x,y,t,min1,head,tail,tot,u; 6 int a[801][801],b[501],dis[801],num[801],w[801][801],team[1601]; 7 bool exist[801]; 8 int main() { 9     freopen("butter.in","r",stdin);10     freopen("butter.out","w",stdout);11     cin>>n>>p>>c;12     for(i=1; i<=p; i++) {13         b[i]=0;14         num[i]=0;15         for(j=1; j<=p; j++)16             w[i][j]=0x7fffffff/3;17     }18     for(i=1; i<=n; i++)19         cin>>b[i];20     for(i=1; i<=c; i++) {                                  //邻接矩阵存储21         cin>>x>>y>>t;22         w[x][y]=t;23         a[x][++num[x]]=y;24         a[y][++num[y]]=x;25         w[y][x]=w[x][y];26     }27     min1=0x7fffffff/3;28     for(i=1; i<=p; i++) {29         for(j=1; j<=p; j++) dis[j]=0x7fffffff/3;30         memset(team,0,sizeof(team));                         //队列数组初始化31         memset(exist,false,sizeof(exist));                   //exist标志初始化32         dis[i]=0;33         team[1]=i;34         head=0;35         tail=1;36         exist[i]=true;      //起始点入队37         do {38             head++;39             head=((head-1)%1601)+1;                           //循环队列处理40             u=team[head];41             exist[u]=false;42             for(j=1; j<=num[u]; j++)43                 if (dis[a[u][j]]>dis[u]+w[u][a[u][j]]) {44                     dis[a[u][j]]=dis[u]+w[u][a[u][j]];45                     if (!exist[a[u][j]]) {46                         tail++;47                         tail=((tail-1)%1601)+1;48                         team[tail]=a[u][j];49                         exist[a[u][j]]=true;50                     }51                 }52         } while(head!=tail);53         tot=0;54         for(j=1; j<=n; j++)55             tot+=dis[b[j]];56         if (tot

5 并查集

普遍代码：

1 #include
       
         2 #include
        
          3 using namespace std; 4 #define maxn 20001 5 int father[maxn]; 6 　　int m,n,i,x,y,q; 7 　　/* 8 　　int find(int x)                  //用非递归的实现 9 　　{10 　　    while (father[x] != x) x= father[x];11 　　    return x;12 　　}13 　　*/14 　　int find(int x)                  //用递归的实现15 　　 {16     　　    if (father[x] != x) father[x] = find(father[x]);  //路径压缩17     　　    return father[x];18     　　19 }20 　　void unionn(int r1,int r2)21 　　 {22     　　    father[r2] = r1;23     　　24 }25 　　26 int main()27 　　 {28     　　    freopen("relation.in","r",stdin);29     　　    freopen("relation.out","w",stdout);30     　　    cin >> n >> m;31     　　    for (i = 1; i <= n; i++)32         　　        father[i] = i;           //建立新的集合，其仅有的成员是i33     　　    for (i = 1; i <= m; i++)34         　　    {35         　　        scanf("%d%d",&x,&y);36         　　        int r1 = find(x);37         　　        int r2 = find(y);38         　　        if (r1 != r2) unionn(r1,r2);39         　　40     }41     　　    cin >> q;42     　　    for (i = 1; i <= q; i++)43         　　    {44         　　        scanf("%d%d",&x,&y);;45         　　              if (find(x) == find(y)) printf("Yes\n")                       else printf("No\n");        　　                        }             return 0;50     　　51 }

经典例题：家谱树 codevs

6 prim 经典代码

算法采用与Dijkstra、Bellman-Ford算法一样的“蓝白点”思想：白点代表已经进入最小生成树的点，蓝点代表未进入最小生成树的点。算法描述：以1为起点生成最小生成树，min[v]表示蓝点v与白点相连的最小边权。MST表示最小生成树的权值之和。a）初始化：min[v]= ∞(v≠1); min[1]=0;MST=0;b）for (i = 1; i<= n; i++)1.寻找min[u]最小的蓝点u。2.将u标记为白点3.MST+=min[u]4.for 与白点u相连的所有蓝点v                   if (w[u][v]

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 int g[101][101];              //邻接矩阵 6 int minn[101];                //minn[i]存放蓝点i与白点相连的最小边权 7 bool u[101];                  //u[i]=True，表示顶点i还未加入到生成树中 8                               //u[i]=False，表示顶点i已加入到生成树中  9 int n,i,j;10 int main()11 {12     freopen("wire.in","r",stdin);13     freopen("wire.out","w",stdout);14     cin >> n;15     for (i = 1; i <= n; i++)16         for (j = 1; j <= n; j++)17             cin >> g[i][j];           18     memset(minn,0x7f,sizeof(minn));   //初始化为maxint19     minn[1] = 0;20     memset(u,1,sizeof(u));            //初始化为True，表示所有顶点为蓝点21 for (i = 1; i <= n; i++)22     {23         int k = 0;24         for (j = 1; j <= n; j++)     //找一个与白点相连的权值最小的蓝点k25             if (u[j] && (minn[j] < minn[k]))26                 k = j;27         u[k] = false;                    //蓝点k加入生成树，标记为白点28         for (j = 1; j <= n; j++)         //修改与k相连的所有蓝点29             if (u[j] && (g[k][j] < minn[j]))30                  minn[j] = g[k][j]; 31     }       32     int total = 0;33     for (i = 1; i <= n; i++)             //累加权值 34         total += minn[i];35     cout << total << endl;36     return 0;37 }

7 克鲁斯卡尔

1 算法描述: 2 初始化并查集。father[x]=x。 3 tot=0 4 将所有边用快排从小到大排序。 5 计数器 k=0; 6 for (i=1; i<=M; i++)      //循环所有已从小到大排序的边 7   if  这是一条u,v不属于同一集合的边(u,v)(因为已经排序，所以必为最小)， 8     begin 9     　①合并u,v所在的集合，相当于把边(u,v)加入最小生成树。10 　    ②tot=tot+W(u,v)11       ③k++12       ④如果k=n-1,说明最小生成树已经生成，则break; 13     end;14 6. 结束，tot即为最小生成树的总权值之和。*/

经典代码

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 struct k{ 6     int x,y,v; 7      8 }a[10000]; 9 int fa[1000];10 int find(int x)11 {12     if(fa[x]!=x)13     {fa[x]=find(fa[x]);14     return fa[x];15     }16     else17     return x;18 }19 void un(int x,int y)20 {21     fa[x]=y;22 }23 int cmp( k a, k b)      24 {25      if (a.v < b.v) return 1;26         else return 0; 27 }28 int main()29 {30     int s,m=0;31     int n;32     cin>>n;33     for(int i=1;i<=n;i++)34      {35          for(int j=1;j<=n;j++)36           {37               cin>>s;38               if(s!=0)39                {40                    m++;41                    a[m].x=i;42                    a[m].y=j;43                    a[m].v=s;44                }45           }46      }47      for(int i=1;i<=n;i++)48       {49           fa[i]=i;50       }51       sort(a+1,a+m+1,cmp);52       int k=0,tot=0;53      for(int i=1;i<=m;i++)54       {55           int r=find(a[i].x);56           int rr=find(a[i].y);57           if(r!=rr)58            {59                un(r,rr);60                tot+=a[i].v;61                k++;62            }63         if(k==n-1)64          {65              break;66          }67       }68       cout<