本文主要是介绍UVA-1658 Admiral，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出v个点，e条边的加权有向图，求1-v的两条不相交的路径，使得劝和最小。
思路：
拆点法，把2-（v-1）的每个节点拆成两个结点，中间连一条容量为1，费用为0的边，求1到v的流量为1的最小费用流即可。
#include <bits/stdc++.h>using namespace std;
const int maxn=1e4;
int n,m;
const int inf=1e8;
struct Edge
{int from,to,flow,cap,cost;Edge(int f,int t,int c,int ff,int cc){from=f;to=t;flow=ff;cap=c;cost=cc;}
};
vector<int> G[maxn];
int p[maxn];
int a[maxn];
vector<Edge>edges;
int d[maxn];
int inq[maxn];
void Init()
{edges.clear();for(int i=0; i<maxn; i++) G[i].clear();
}
void addEdges(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));int t=edges.size();G[from].push_back(t-2);G[to].push_back(t-1);
}
bool BellmanFord(int s,int t,int &flow,long long int &cost)
{for(int i=0; i<2*n+10; i++) d[i]=inf;memset(inq,0,sizeof(inq));d[s]=0;inq[s]=1;p[s]=0;a[s]=inf;queue<int> q;q.push(s);while(!q.empty()){int u=q.front();q.pop(),inq[u]=0;for(int i=0; i<G[u].size(); i++){Edge &e=edges[G[u][i]];if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){d[e.to]=d[u]+e.cost;p[e.to]=G[u][i];a[e.to]=min(a[u],e.cap-e.flow);if(!inq[e.to]){q.push(e.to);inq[e.to]=1;}}}}if(d[t]==inf) return false;cost+=(long long int)d[t]*(long long int)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 MincostMaxflow(int s,int t,long long int &cost)
{int flow=0;cost=0;while(BellmanFord(s,t,flow,cost));return flow;
}
int main()
{while(cin>>n>>m){if(m+n==0) break;Init();for(int i=2; i<n; i++)addEdges(i,i+n,1,0);for(int i=1; i<=m; i++){int u,v,c;cin>>u>>v>>c;if(u!=1&&u!=n) addEdges(u+n,v,1,c);else addEdges(u,v,1,c);}long long int ans;addEdges(0,1,2,0);addEdges(n,n*2+1,2,0);MincostMaxflow(0,2*n+1,ans);cout<<ans<<endl;}return 0;
}
这篇关于UVA-1658 Admiral的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
