BZOJ 1927: [Sdoi2010]星际竞速(费用流）-白红宇

BZOJ 1927: [Sdoi2010]星际竞速(费用流）

阅读量：4521 次

发布时间：2019-06-08

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

解题思路

　　仿照最小路径覆盖问题，用费用流解决此题。最小路径覆盖问题是拆点连边后用\(n-\)最大匹配，这里的话也是将每个点拆点，源点向入点连流量为\(1\)，费用为\(0\)的边，向出点连流量为\(1\)，费用为\(a[i]\)的边，出点向汇点连流量为\(1\)，费用为\(0\)的边。然后对于每条边，由\(x\)的入点向\(y\)的出点连流量为\(1\)，费用为路径长度的边。跑一遍费用流。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAXN = 1605;const int MAXM = 20005;const int inf = 0x3f3f3f3f;typedef long long LL;inline int rd(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();    return f?x:-x;}inline int min(int x,int y){    return x

Q;inline void add(int bg,int ed,int w,int z){ to[++cnt]=ed,nxt[cnt]=head[bg],val[cnt]=w,cost[cnt]=z,head[bg]=cnt;}inline bool spfa(){ memset(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis)); while(Q.size()) Q.pop(); dis[S]=0;vis[S]=1;Q.push(S);incf[S]=inf; while(Q.size()){ int x=Q.front();Q.pop();vis[x]=0; for(int i=head[x];i;i=nxt[i]){ int u=to[i]; if(dis[x]+cost[i]

y) swap(x,y); add(x,y+n,1,z),add(y+n,x,0,-z); } while(spfa()) update(); printf("%lld\n",ans); return 0;}

转载于:https://www.cnblogs.com/sdfzsyq/p/10117957.html

你可能感兴趣的文章