問題

分析

還是構(gòu)圖，為了讓兩條路徑?jīng)]有公共點(diǎn)，所以將除了1，v外的其他點(diǎn)拆分成兩個點(diǎn)，一個點(diǎn)上連接原來的入弧，另一個點(diǎn)連接出弧，然后兩個點(diǎn)之間連接一條容量1，費(fèi)用為0的邊，這樣就能夠保證只有1個流量經(jīng)過這個點(diǎn)，如果兩個流量在此點(diǎn)重合，那么一定有一個不能出去，所以可以使用最大流最小費(fèi)用算法求解

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <vector> #include <utility> #include <map> #include <string> #include <queue> using namespace std; const int maxn=2005,Inf=0x3f3f3f3f;struct Edge{int from,to,cap,flow,cost;Edge(int u,int v,int cap,int flow,int cost):from(u),to(v),cap(cap),flow(flow),cost(cost){} };struct MCMF{int n,m;vector<Edge> edges;vector<int> G[maxn];int a[maxn];int p[maxn];int d[maxn]; //bellman-fordint inq[maxn]; //是否在隊列中void init(int n){this->n=n;for(int i=0;i<n;++i) G[i].clear();edges.clear();}void AddEdge(int from,int to,int cap,int cost){edges.push_back(Edge(from,to,cap,0,cost));edges.push_back(Edge(to,from,0,0,-cost));m=edges.size();G[from].push_back(m-2);G[to].push_back(m-1);}bool BellmanFord(int s,int t,int &flow,long long &cost){for(int i=0;i<n;++i) d[i]=Inf;memset(inq,0,sizeof(inq));p[s]=0; a[s]=Inf; d[s]=0; inq[s]=1;queue<int> Q;Q.push(s);while(!Q.empty()){int x=Q.front();Q.pop();inq[x]=0;for(int i=0;i<G[x].size();++i){Edge &e=edges[G[x][i]];if(d[e.to]>d[x]+e.cost && e.cap>e.flow){d[e.to]=d[x]+e.cost;p[e.to]=G[x][i];a[e.to]=min(a[x],e.cap-e.flow);if(!inq[e.to]){inq[e.to]=1;Q.push(e.to);}}}}if(d[t]==Inf) return false;flow+=a[t];cost+=(long long)d[t]*a[t];for(int u=t;u!=s;u=edges[p[u]].from){edges[p[u]].flow+=a[t];edges[p[u]^1].flow-=a[t];}return true;}int MincostFlow(int s,int t,long long &cost){int flow=0;cost=0;while(flow<2 && BellmanFord(s,t,flow,cost));return flow;} };int n,m,a,b,c; MCMF mcmf; int main(void){while(scanf("%d%d",&n,&m)==2){int t=2*n;mcmf.init(t);//將每個點(diǎn)拆成兩個點(diǎn)，入點(diǎn)和出點(diǎn) 入點(diǎn)編號2~n-1,出點(diǎn)標(biāo)號n+1~2*n-2//新加入一個點(diǎn)0，0和點(diǎn)1之間有邊，容量是2,費(fèi)用是0mcmf.AddEdge(0,1,2,0);for(int i=2;i<n;++i) mcmf.AddEdge(i,n-1+i,1,0);for(int i=0;i<m;++i){scanf("%d%d%d",&a,&b,&c);if(a!=1 && a!=n) a=n-1+a;mcmf.AddEdge(a,b,1,c);}long long cost=0;mcmf.MincostFlow(0,n,cost);printf("%lld\n",cost);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Admiral UVA - 1658的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。