运输问题(网络流24)-白红宇

运输问题(网络流24)

阅读量：5139 次

发布时间：2019-06-13

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

运输问题

建模之后就是费用流板题。建模方法就是两边一排。

注意重置边的时候，不能swap，要用\(+=\)原因思考一下显然，不然就会不知道哪里错了。

强行总结的话，这样的建模体现了一个且的关系。

//@winlere#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;  typedef long long ll;inline int qr(){      register int ret=0,f=0;      register char c=getchar();      while(c<48||c>57)f|=c==45,c=getchar();      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();      return f?-ret:ret;}const int maxn=25050;int n,m,S,T,nodecnt;const int inf=0x3f3f3f3f;struct E{      int to,nx,c,w;}e[maxn<<2|1];int head[maxn];int cnt=-1;inline void add(const int&fr,const int&to,const int&w,const int&c,const bool&f){      //printf("fr=%d to=%d w=%d c=%d\n",fr,to,w,c);      e[++cnt]={to,head[fr],c,w};      head[fr]=cnt;      if(f)add(to,fr,0,-c,0);}inline int mincost(){      int cost=0,fl=0;      int d[maxn],last[maxn],flow[maxn],in[maxn];      queue 
         
           q; while(1){ while(!q.empty())q.pop(); for(register int t=0;t<=m+n+2;++t) d[t]=inf,flow[t]=0,last[t]=0,in[t]=0; d[S]=0;flow[S]=inf; q.push(S); while(!q.empty()){ register int now=q.front(); in[now]=0; q.pop(); //cout<<"now="<
          
           <
           
            0&&d[e[t].to]>d[now]+e[t].c){ //cout<
            
             <

q; int cost=0,fl=0; int d[maxn],last[maxn],flow[maxn],in[maxn]; while(1){ while(!q.empty())q.pop(); for(register int t=0;t<=m+n+20;++t) d[t]=-inf,flow[t]=0,last[t]=0,in[t]=0; d[S]=0;flow[S]=inf; q.push(S); while(!q.empty()){ register int now=q.front(); in[now]=0; q.pop(); //cout<<"now="<

(t^1)){ e[t^1].w+=e[t].w; e[t].w=0; } printf("%d\n",maxcost()); return 0;}

转载于:https://www.cnblogs.com/winlere/p/11234624.html

你可能感兴趣的文章