费用流板子 dij&spfa

本是古典何须时尚 2021-10-30 01:04 314阅读 0赞

dij

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

struct edge{
        int to,cap,cost,rev;
    };
    
    int n,V,k;
    int a[MAX_N];
    vector<edge> G[2*MAX_N+2];
    int h[2*MAX_N+2];
    int dist[2*MAX_N+2];
    int prevv[2*MAX_N+2],preve[2*MAX_N+2];
    
    void add_edge(int from,int to,int cap,int cost){
        G[from].push_back((edge){to,cap,cost,G[to].size()});
        G[to].push_back((edge){
          from,0,-cost,G[from].size()-1});
    }
    
    int min_cost_flow(int s,int t,int f){
        int res=0;
        fill(h,h+V,0);
        while(f>0){
            priority_queue<P,vector<P>,greater<P> >que;
            fill(dist,dist+V,INF);
            dist[s]=0;
            que.push(P(0,s));
            while(!que.empty()){
                P p=que.top();que.pop();
                int v=p.second;
                if(dist[v]<p.first)continue;
                for(int i=0;i<G[v].size();i++){
                    edge &e=G[v][i];
                    if(e.cap>0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
                        dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
                        prevv[e.to]=v;
                        preve[e.to]=i;
                        que.push(P(dist[e.to],e.to));
                    }
                }
            }
            if(dist[t]==INF)return -1;
            for(int v=0;v<V;v++)h[v]+=dist[v];
            int d=f;
            for(int v=t;v!=s;v=prevv[v]){
                d=min(d,G[prevv[v]][preve[v]].cap);
            }
            f-=d;
            res+=d*h[t];
            for(int v=t;v!=s;v=prevv[v]){
                edge &e=G[prevv[v]][preve[v]];
                e.cap-=d;
                G[v][e.rev].cap+=d;
            }
        }
        return res;
    }

spfa

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

int head[maxn],Next[maxn*200],to[maxn*200];
    int flow[maxn*200],dis[maxn],pre[maxn],vis[maxn],id[maxn],ct[maxn];
    inline void add(int u,int v,int w,int cost){
        Next[cnt]=head[u];
        head[u]=cnt;
        to[cnt]=v;
        flow[cnt]=w;
        ct[cnt++]=cost;
    
        Next[cnt]=head[v];
        head[v]=cnt;
        to[cnt]=u;
        flow[cnt]=0;
        ct[cnt++]=-cost;
    }
    bool spfa(){
        memset(vis,0,sizeof(vis));
        memset(dis,inf,sizeof(dis));
        memset(pre,-1,sizeof(pre));
        dis[s]=0;
        queue<int> q;
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u];i!=-1;i=Next[i]){
                int v=to[i];
                int d=ct[i];
                if(dis[v]>dis[u]+d&&flow[i]>0){
                    dis[v]=dis[u]+d;
                    pre[v]=u;
                    id[v]=i;
                    if(!vis[v]){
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
        }
       // cout<<dis[t]<<endl;
        return dis[t]<inf;
    }
    int Maxflow(){
        int ans=0;
        while(spfa()){ 
            int Min=inf;
            for(int i=t;i!=s;i=pre[i]){
            //    cout<<i<<" "<<pre[i]<<endl;
                Min=min(flow[id[i]],Min);
            }
            for(int i=t;i!=s;i=pre[i]){
                flow[id[i]]-=Min;
                flow[id[i]^1]+=Min;
            }
            ans+=dis[t]*Min;
           
        }
        return ans;
    }

转载于:https://www.cnblogs.com/MengX/p/11336433.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/5304c02fd00741a5a9f55f719b72ffd4.png