《图》算法专题C中，有哪些长尾词算法应用案例？

本文共计3196个文字，预计阅读时间需要13分钟。

1. Floyd算法+【题目描述】平面上有n个点（n=100），每个点的坐标均位于-10000~10000之间。其中，一些点之间有连线。若有连线，则表示两点之间存在通路。

1、Floyd算法

平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。

若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。

共n+m+3行，其中:

第一行为整数n。

第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。

第n+2行为一个整数m，表示图中连线的个数。

此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。

最后一行：两个整数s和t，分别表示源点和目标点。

一行，一个实数（保留两位小数），表示从s到t的最短路径长度。

5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5 3.41

#include<iostream> #include<cmath> #include<cstring> using namespace std; const int N=105; int a[N][3];// 一维存储点的编号，二维存储点的x、y坐标 double dis[N][N]; int main() { int n,m,s,t,x,y; memset(dis,0x7f,sizeof(dis));// double 数组初始化用 0x7f cin>>n; for(int i=1;i<=n;i++) { cin>>a[i][1]>>a[i][2]; } cin>>m; for(int i=1;i<=m;i++) { cin>>x>>y; dis[y][x]=dis[x][y]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));// 距离的初始化 } cin>>s>>t; // 算法主体 for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if((i!=j) && (i!=k) && (j!=k) && (dis[i][k]+dis[k][j]<dis[i][j])) { dis[i][j]=dis[i][k]+dis[k][j]; } } } } printf("%.2lf",dis[s][t]); return 0; }

2、Dijkstra算法

题目同上

#include<iostream> #include<cmath> #include<cstring> using namespace std; const double INF=1e30; const int N=105; int n,m,S,T,x,y; int a[N][3]; double dis[N][N]; double d[N]; bool vis[N]={false}; void dijkstra(int s,int t) { memset(d,0x7f,sizeof(d)); d[s]=0;// 起点到自身的距离为0 for(int i=1;i<=n;i++) { int u=-1; double MIN=INF; for(int j=1;j<=n;j++) { if(!vis[j]&&d[j]<MIN) { u=j; MIN=d[j]; } } if(u==-1)return; vis[u]=true; for(int v=1;v<=n;v++) { if(!vis[v]&&dis[u][v]<INF&&d[u]+dis[u][v]<d[v]) { d[v]=d[u]+dis[u][v]; } } } } int main() { memset(dis,0x7f,sizeof(dis)); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i][1]>>a[i][2]; } cin>>m; for(int i=1;i<=m;i++) { cin>>x>>y; dis[y][x]=dis[x][y]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2)); } cin>>S>>T; dijkstra(S,T); printf("%.2lf",d[T]); return 0; }

3、牛的旅行-Floyd算法

农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在农场里添加一条路径 ( 注意，恰好一条 )。对这条路径有这样的限制：一个牧场的直径就是牧场中最远的两个牧区的距离 ( 本题中所提到的所有距离指的都是最短的距离 )。考虑如下的两个牧场，图１是有5个牧区的牧场，牧区用“*”表示，路径用直线表示。每一个牧区都有自己的坐标：

图１所示的牧场的直径大约是12.07106, 最远的两个牧区是A和E，它们之间的最短路径是A-B-E。

这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。

现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。

第 1 行：一个整数N (1 <= N <= 150), 表示牧区数；

第 2 到 N+1 行：每行两个整数X，Y ( 0 <= X，Y<= 100000 )， 表示N个牧区的坐标。每个牧区的坐标都是不一样的。

第 N+2 行到第 2*N+1 行：每行包括N个数字 ( 0或1 ) 表示一个对称邻接矩阵。

例如，题目描述中的两个牧场的矩阵描述如下：

A B C D E F G H A 0 1 0 0 0 0 0 0 B 1 0 1 1 1 0 0 0 C 0 1 0 0 1 0 0 0 D 0 1 0 0 1 0 0 0 E 0 1 1 1 0 0 0 0 F 0 0 0 0 0 0 1 0 G 0 0 0 0 0 1 0 1 H 0 0 0 0 0 0 1 0 输入数据中至少包括两个不连通的牧区。

只有一行，包括一个实数，表示所求答案。数字保留六位小数。

8 10 10 15 10 20 10 15 15 20 15 30 15 25 10 30 10 01000000 10111000 01001000 01001000 01110000 00000010 00000101 00000010 22.071068

#include<iostream> #include<cmath> #include<cstring> using namespace std; const int N=155; int n; double INF=1e12; double minx=1e20; double x[N]; double y[N]; double m[N]; double dis[N][N]; double fun(int i,int j) { return sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2)); } int main() { cin>>n; char c; for(int i=1;i<=n;i++) { cin>>x[i]>>y[i]; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>c; if(c=='1') { dis[i][j]=fun(i,j); }else { dis[i][j]=INF; } } } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=j&&i!=k&&j!=k) { if(dis[i][k]<INF-1&&dis[k][j]<INF-1) { if(dis[i][k]+dis[k][j]<dis[i][j]) { dis[i][j]=dis[i][k]+dis[k][j]; } } } } } } memset(m,0,sizeof(m)); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(dis[i][j]<INF-1&&m[i]<dis[i][j]) { m[i]=dis[i][j]; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=j&&dis[i][j]>INF-1)// double型数据的大小比较一般不使用== { double temp=fun(i,j); if(m[i]+m[j]+temp<minx) { minx=m[i]+m[j]+temp; } } } } for(int i=1;i<=n;i++) { if(m[i]>minx) { minx=m[i]; } } printf("%.6lf",minx); return 0; }

4、香甜的黄油--spfa算法

农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1≤N≤500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

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

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

第一行: 三个数：奶牛数N，牧场数P（2≤P≤800），牧场间道路数C(1≤C≤1450)。

第二行到第N+1行: 1到N头奶牛所在的牧场号。

第N+2行到第N+C+1行：每行有三个数：相连的牧场A、B，两牧场间距（1≤D≤255），当然，连接是双向的。

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

3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5 8

#include<iostream> #include<cmath> #include<cstring> #include<vector> #include<queue> using namespace std; const int INF=0x7fffffff; const int N=805;// 牧场的最大数量 int cow[510];//奶牛所在的牧场编号 int n,p,c; struct Node { int v;//边的终点编号 int w;//边权，即两个牧场间的距离 Node(int _v,int _w):v(_v),w(_w){};//构造函数 }; vector<Node> Adj[N];// 建立邻接表，数组中的每一个元素都是vector，vector的每个元素都是Node类型 int d[N];//源点到各点最短路径 int num[N];//各点入队次数 bool inq[N];//是否在队列中 bool spfa(int s)//源点 { //初始化 fill(d,d+N,INF); memset(num,0,sizeof(num)); memset(inq,false,sizeof(inq)); // 建立队列 queue<int>q; //对源点操作 d[s]=0; q.push(s); inq[s]=true; num[s]++; while(!q.empty()) { int u=q.front(); q.pop();//队首出队 inq[u]=false;//出队后即不在队列中 //遍历u的所有邻接边 for(unsigned i=0;i<Adj[u].size();i++) { int v=Adj[u][i].v; int w=Adj[u][i].w; if(d[u]+w<d[v])//松弛操作 { d[v]=d[u]+w; if(!inq[v])// 如果此时v不在队列中，可以入队 { q.push(v); inq[v]=true; num[v]++; if(num[v]>=n)return false;// 当该点的入队次数大于顶点数时，说明存在可达负环，需要退出算法 } } } } return true; } int main() { cin>>n>>p>>c; for(int i=1;i<=n;i++) { cin>>cow[i]; } int x,y,dis; for(int i=1;i<=c;i++) { cin>>x>>y>>dis; Adj[x].push_back(Node(y,dis));// 点x的邻接边有y Adj[y].push_back(Node(x,dis)); } int minDis=INF; for(int i=1;i<=p;i++) { spfa(i);//枚举每个牧场，作为当前源点 int total=0;// 在当前源点下，所有奶牛行走的最小距离 for(int j=1;j<=n;j++) { total+=d[cow[j]];//累加每个奶牛的行走距离 } if(total<minDis) { minDis=total;//每枚举一个源点，更新最小距离 } } cout<<minDis; return 0; }

5、信使--Floyd

战争时期，前线有n个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在第一个哨所。当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。直至所有n个哨所全部接到命令后，送信才算成功。因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他k个哨所有通信联系的话，这个哨所内至少会配备k个信使）。

现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。

第1行有两个整数n和m，中间用1个空格隔开，分别表示有n个哨所和m条通信线路,且1≤n≤100。

第2至m+1行：每行三个整数i、j、k，中间用1个空格隔开，表示第i个和第j个哨所之间存在通信线路，且这条线路要花费k天。

一个整数，表示完成整个送信过程的最短时间。如果不是所有的哨所都能收到信，就输出-1。

4 4 1 2 4 2 3 7 2 4 1 3 4 6 11

#include<iostream> #include<cmath> #include<cstring> #include<vector> #include<queue> using namespace std; const int INF=0x7fffffff; const int N=105; int dis[N][N]; int main() { int n,m,x,y,d; cin>>n>>m; fill(dis[0],dis[0]+N*N,INF);//初始化用fill for(int i=1;i<=m;i++) { cin>>x>>y>>d; dis[x][y]=dis[y][x]=d;//无向图 } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=j&&i!=k&&j!=k) { if(dis[i][k]<INF&&dis[k][j]<INF)//判断是否可以优化 { if(dis[i][k]+dis[k][j]<dis[i][j]) { dis[i][j]=dis[i][k]+dis[k][j]; } } } } } } int day=-10000;// 最短时间就是指挥所到其他的一个哨所的最大距离 for(int i=1;i<=n;i++) { if(dis[1][i]!=INF&&dis[1][i]>day) { day=dis[1][i]; } } if(day<0) { cout<<-1; }else { cout<<day; } return 0; }