?

【題目鏈接】?http://poj.org/problem?id=2135

?

【題目大意】

　　有一張無向圖，求從1到n然后又回來的最短路
　　同一條路只能走一次

?

【題解】

　　題目等價于求從1到n的兩條路，使得兩條路的總長最短
　　那么就等價于求總流量為2的費用流

?

【代碼】

#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <utility> using namespace std; const int INF=0x3f3f3f3f; typedef pair<int,int> P; struct edge{int to,cap,cost,rev;}; const int MAX_V=1000; int V,h[MAX_V],dist[MAX_V],prevv[MAX_V],preve[MAX_V]; vector<edge> G[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;fill(h,h+V,0);while(f>0){priority_queue<P,vector<P>,greater<P> > que;fill(dist,dist+V,INF);dist[s]=0;que.push(P(0,s));while(!que.empty()){P p=que.top(); que.pop();int v=p.second;if(dist[v]<p.first)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+h[v]-h[e.to]){dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];prevv[e.to]=v;preve[e.to]=i;que.push(P(dist[e.to],e.to));}}}if(dist[t]==INF)return -1;for(int v=0;v<V;v++)h[v]+=dist[v];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*h[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; } const int MAX_M=10000; int N,M; int a[MAX_M],b[MAX_M],c[MAX_M]; void init(){for(int i=0;i<M;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]); } void solve(){int s=0,t=N-1;V=N;for(int i=0;i<N;i++)G[i].clear();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(){while(~scanf("%d%d",&N,&M)){init();solve();}return 0; }

轉載于:https://www.cnblogs.com/forever97/p/poj2135.html

總結

以上是生活随笔為你收集整理的POJ 2135 Farm Tour （费用流）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。