有哪些做分析图用的地图网站/陕西seo公司

传送门

题意：农夫的朋友前来拜访，于是他带领大家参观它的农场，农场里有N块地，其中农夫的家在1号地，而N号地有个很大的仓库。农场内有M条道路(双向通行)，道路i连接着ai号地和bi号地，长度为ci。农夫希望按照从家里出发，经过若干地后达到仓库，然后再返回家中的顺序待朋友参观。如果要求往返不能经过同一道路两次，求参观路线总长度的最小值。

题解：只考虑去或者回的情况，那么问题只不过是无向图中两点之间的最短路而已。但现在既要去又要回，并且不能经过相同的道路的这一限制。那么，如果先计算去时的最短路，然后将所用的道路删去，再在剩下的图上计算回来时的最短路，这样是否可行呢？有很多反例，不总能找到最优结果，放弃把问题当作去和回的这种想法，转而将问题当作从1号顶点到N号顶点的两条没有公共边的路径，这样转化后，就不过是求流量为2的最小费用流了。

附上代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>using namespace std;const int MAX_M=1e4+50;
const int MAX_V=1e3+50;
const int INF=0x3f3f3f3f;int N,M;
int a[MAX_M],b[MAX_M],c[MAX_M];
struct edge{int to,cap,cost,rev;edge(int _to,int _cap,int _cost,int _rev):to(_to),cap(_cap),cost(_cost),rev(_rev){}
};int V;
vector<edge>G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];void add_edge(int from,int to,int cap,int cost)
{G[from].push_back(edge(to,cap,cost,G[to].size()));G[to].push_back(edge(from,0,-cost,G[from].size()-1));
}int min_cost_flow(int s,int t,int f)
{int res=0;while(f>0){fill(dist,dist+V,INF);dist[s]=0;bool update=true;while(update){update=false;for(int v=0;v<V;v++){if(dist[v]==INF){continue;}for(int i=0;i<G[v].size();i++){edge &e=G[v][i];if(e.cap>0&&dist[e.to]>dist[v]+e.cost){dist[e.to]=dist[v]+e.cost;prevv[e.to]=v;preve[e.to]=i;update=true;}}}}if(dist[t]==INF){return -1;}int d=f;for(int v=t;v!=s;v=prevv[v]){d=min(d,G[prevv[v]][preve[v]].cap);}f-=d;res+=d*dist[t];for(int v=t;v!=s;v=prevv[v]){edge &e=G[prevv[v]][preve[v]];e.cap-=d;G[v][e.rev].cap+=d;}}return res;
}void solve()
{int s=0,t=N-1;V=N;for(int i=0;i<M;i++){add_edge(a[i]-1,b[i]-1,1,c[i]);add_edge(b[i]-1,a[i]-1,1,c[i]);}printf("%d\n",min_cost_flow(s,t,2));
}int main()
{scanf("%d%d",&N,&M);for(int i=0;i<M;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);}solve();return 0;
}