UVA-1658 Admiral-白红宇

UVA-1658 Admiral

阅读量：4113 次

发布时间：2019-05-25

本文共 1599 字，大约阅读时间需要 5 分钟。

题意：给出v个点，e条边的加权有向图，求1-v的两条不相交的路径，使得劝和最小。

思路：

拆点法，把2-（v-1）的每个节点拆成两个结点，中间连一条容量为1，费用为0的边，求1到v的流量为1的最小费用流即可。

#include 
   
    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
    
      G[maxn];int p[maxn];int a[maxn];vector
     
      edges;int d[maxn];int inq[maxn];void Init(){    edges.clear();    for(int i=0; i

q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(),inq[u]=0; for(int i=0; i

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

>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<

转载地址：http://ffgsi.baihongyu.com/

你可能感兴趣的文章