旅游路线问题线性规划网络流

旅游路线问题

在这里插入图片描述

#include <iostream>在这里插入图片描述#include <cstring>
#include <map>
#include <queue>
using namespace std;
using std::cout;
const int INF = 1000000;    //正无穷
const int NODESIZE = 100;   //结点最大个数
const int EDGESIZE = 10000; //最大边数
int top;                    //当前边下标
int maxflow;                //最大流最小费用
bool vis[NODESIZE];         //访问标记数组
int c[NODESIZE];            //入队次数
int dist[NODESIZE];         //dist[i]表示源点到点i最短距离:距离即这条路单位cost和
int pre[NODESIZE];          //前驱数组
string str[NODESIZE];
map<string, int> maze;struct Vertex
{              //邻接表头节点int first; //与之连接的边的序号
} V[NODESIZE];
struct Edge
{                //边表示int v, next; //v弧头 next指向下一条邻接边int cap, flow, cost;
} E[EDGESIZE];void init();                                  //初始化
void add(int u, int v, int c, int cost);      //更新混合网络
void add_edge(int u, int v, int c, int cost); //更新混合网络边
void printgraph(int n);                       //输出网络邻接表
void printflow(int n);                        //输出实流边
int MCMF(int s, int t, int n);                //最小花费最大流
bool SPFA(int s, int t, int n);               //求最小费用路
void print(int s, int t);int main(int argc, char **argv)
{int n, m, i;string str1, str2;cout << "输入景点个数n和直达路线数m:\n";cin >> n >> m;init();maze.clear();cout << "输入景点名字\n";for (i = 1; i <= n; i++){cin >> str[i];maze[str[i]] = i;if (i == 1 || i == n){add(i, i + n, 2, 0);}else{add(i, i + n, 1, 0);}}cout << "输入可以直达的两个景点名\n";for (i = 1; i <= m; i++){cin >> str1 >> str2;int a = maze[str1], b = maze[str2];if (a < b){if (a == 1 && b == n){add(a + n, b, 2, -1);}else{add(a + n, b, 1, -1);}}else{if (b == 1 && a == n){add(b + n, a, 2, -1);}else{add(b + n, a, 1, -1);}}}cout << "最多经过景点个数:" << 0 - MCMF(1, 2 * n, 2 * n) << endl;cout << "依次经过景点:\n";cout << str[1] << endl;memset(vis, 0, sizeof(vis));print(1, n);cout << str[1] << endl;return 0;
}//初始化
void init()
{memset(V, -1, sizeof(V)); //初始化顶点top = 0;                  //当前边下标maxflow = 0;
}//更新混合网络
void add(int u, int v, int c, int cost)
{add_edge(u, v, c, cost);add_edge(v, u, 0, -cost);
}//更新混合网络边
void add_edge(int u, int v, int c, int cost)
{//    top    top.v//u---------->v//构建邻接表：头插法 顺序存储法E[top].v = v;E[top].cap = c;E[top].flow = 0;E[top].cost = cost;E[top].next = V[u].first; //.next记录链的结点，下一个边的下标V[u].first = top++;       //顺序存储拉链
}
//输出网络邻接表
void printgraph(int n)
{cout << "\n网络邻接表\n";for (int i = 1; i <= n; i++){cout << "v" << i << " [" << V[i].first;for (int j = V[i].first; ~j; j = E[j].next){cout << "]--[" << E[j].v << "  " << E[j].cap << "  "<< E[j].flow << " " << E[j].cost << " " << E[j].next << "]\n";}cout << "\n";}
}
//输出实流边
void printflow(int n)
{cout << "实流边:\n";for (int i = 1; i <= n; i++){for (int j = V[i].first; ~j; j = E[j].next){if (E[j].flow > 0){cout << "v" << i << "--"<< "v" << E[j].v << " " << E[j].flow << " " << E[j].cost << "\n";}}}
}
//最小花费最大流
int MCMF(int s, int t, int n)
{int d; //可增量int i, mincost;mincost = 0; //maxflow为网络当前最大流量，mincost为网络当前最小费用while (SPFA(s, t, n)){                              //有从s到t的最小费用路d = INF;                   //初始化增流量cout << "增广路径: " << t; //             i       i^1     i       i+1            i      i+1=i^1   i    i-1=i^1for (i = pre[t]; i != -1; i = pre[E[i ^ 1].v]){                                     //i=pre[u.v] u---->v u<----v u---->v u<---v,通俗些就是u-->v就v<---u   v<--u u-->vd = min(d, E[i].cap - E[i].flow); //迭代找最小可增量cout << "--" << E[i ^ 1].v;}cout << "\n";cout << "增流量: " << d << "\n";//更新最大流maxflow += d;//增广路上正向边流量+d 反向边流量-dfor (int i = pre[t]; i != -1; i = pre[E[i ^ 1].v]){E[i].flow += d;E[i ^ 1].flow -= d;}mincost += dist[t] * d; //源点到t的单位花费*新增的流量}return mincost;
}
//求最小费用路
bool SPFA(int s, int t, int n)
{int u, v;queue<int> qu;                   //队列memset(vis, false, sizeof(vis)); //标记结点是否已经访问过了memset(c, 0, sizeof(c));         //入队次数memset(pre, -1, sizeof(pre));    //前驱数组初始化为-1//距离初始化:源点到各个结点的最短距离for (int i = 1; i <= n; i++){dist[i] = INF;}//源点入队vis[s] = true;c[s]++;dist[s] = 0;qu.push(s);while (!qu.empty()){//取队头,并消除标记u = qu.front();qu.pop();vis[u] = false;//遍历结点u的邻接表：即遍历u的所有出度边u--->xfor (int i = V[u].first; i != -1; i = E[i].next){v = E[i].v; //u---->vif (E[i].cap > E[i].flow && dist[v] > dist[u] + E[i].cost){ //松弛操作:这条边还可以增流且借助u-->v比直接到v cost少,如果不可增流则这条边不连通//更新源点--->v costdist[v] = dist[u] + E[i].cost;//记录v的前驱,pre记录的是边-->v 通过这条边最短到v 则v的前驱为这条边的下标pre[v] = i;//检测v是否在队列内if (!vis[v]){ //不在//v结点入队列c[v]++;qu.push(v); //入队vis[v] = true;if (c[v] > n){ //超过入队上上限，则说明有负环return false;}}}}}//最短可增流路径cout << "最短可增流路径数组:\n";cout << "dist[]=>";for (int i = 1; i <= n; i++){cout << " " << dist[i];}cout << "\n";if (dist[t] == INF){ //如果源点到汇点距离为正无穷，则不通:找不出最短可通路径return false;}return true;
}void print(int s, int t)
{cout<<"s->t:"<<s<<" "<<t<<"  "; int v;vis[s] = 1;for (int i = V[s].first; ~i; i = E[i].next){ v = E[i].v;//(E[i].flow>0&&E[i].cost<=0) 正向路线//(E[i].flow<0&&E[i].cost>=0) 反向路线if (!vis[v] && ((E[i].flow > 0 && E[i].cost <= 0) || (E[i].flow < 0 && E[i].cost >= 0))){print(v, t);if (v <= t){cout << str[v] << endl;}}}
}/*test
8 10
zhengzhou
luoyang
xian
chengdu
kangding
xianggelila
motuo
lasa
zhengzhou luoyang
zhengzhou xian
luoyang xian
luoyang chengdu
xian chengdu
xian xianggelila
chengdu lasa
kangding motuo
xianggelila lasa
motuo lasaresult:
最短可增流路径数组:
dist[]=> 0 -1 -2 -3 1000000 -3 1000000 -4 0 -1 -2 -3 1000000 -3 1000000 -4
增广路径: 16--8--14--6--11--3--10--2--9--1
增流量: 1
最短可增流路径数组:
dist[]=> 0 0 -1 -1 1000000 -1 1000000 -2 0 0 0 -1 1000000 -1 1000000 -2
增广路径: 16--8--12--4--10--3--9--1
增流量: 1
最短可增流路径数组:
dist[]=> 0 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
最多经过景点个数:6
依次经过景点:
zhengzhou
luoyang
chengdu
lasa
xianggelila
xian
zhengzhou*/