首页 > 其他分享 >【板子】费用流(zkw/Dinic)

【板子】费用流(zkw/Dinic)

时间:2024-02-05 23:22:58浏览次数:24  
标签:edgeid int ed inq 板子 cost Dinic zkw dis

//lg p3381
#include<bits/stdc++.h>
using namespace std;

#define ll long long 
const int N= (int)5e3+3;
const int M =(int)5e4+4;
const ll INF = 0x3f3f3f3f;

int cur[N];
ll dis[N];
bool vis[N];
bool inq[N];

int edgeid=1;
int head[N];
struct edge {int v,cost,nxt;ll w;} e[2*M];
void addedge(int u,int v,int w,int cost)
{
    edgeid++;
    e[edgeid].v=v;
    e[edgeid].cost=cost;
    e[edgeid].w=w;
    e[edgeid].nxt=head[u];
    head[u]=edgeid;
}

ll mxflow,ans;
int n,m,st,ed;

deque<int> q;
bool Spfa()
{
    memset(dis,INF,sizeof(dis));
    memset(inq,0,sizeof(inq));
    q.push_front(ed);
    dis[ed]=0;
    inq[ed]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        inq[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dis[v]>dis[u]-e[i].cost && e[i^1].w)
            {
                dis[v]=dis[u]-e[i].cost;
                if(!inq[v])
                {
                    if(!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
                    else q.push_back(v);
                    inq[v]=1;
                }
            }
        }
    }
    return (dis[st]<=0x3f3f3f3f);
}

ll Dfs(int u,ll rst)
{
    vis[u]=1;
    if(u==ed || !rst) return rst;
    ll sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].v;
        ll f;
        if(dis[v]==dis[u]-e[i].cost && e[i].w && !vis[v] 
        &&(f=Dfs(v,min(rst,e[i].w))))
        {
            sum+=f;
            rst-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(!rst) break;
        }
    }
    return sum;
}

void Zkw()
{
    while(Spfa())
    {
        do
        {
            for(int i=1;i<=n;i++) cur[i]=head[i];
            memset(vis,0,sizeof(vis));
            ll temp=Dfs(st,INF);
            ans+=dis[st]*temp;
            mxflow+=temp;
        }while(vis[ed]);
    }
}

int main()
{
    cin>>n>>m>>st>>ed;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        ll w,cost;
        scanf("%d%d%lld%lld",&u,&v,&w,&cost);
        addedge(u,v,w,cost);
        addedge(v,u,0,-cost);
    }
    Zkw();
    cout<<mxflow<<" "<<ans;
    return 0;
}

标签:edgeid,int,ed,inq,板子,cost,Dinic,zkw,dis
From: https://www.cnblogs.com/yeyou26/p/18008996

相关文章

  • 【板子】网络流(Dinic)
    #include<bits/stdc++.h>usingnamespacestd;constintN=205;constintM=205;constintINF=0x3f3f3f3f;intedgeid=2;inthead[N];structedge{intv,w,nxt;}e[M*2];inlinevoidaddedge(intu,intv,intw){e[edgeid].v=v;e[ed......
  • 板子汇总
    可持久化线段树例题#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=2e5+9;intn,q,a[N],b[N];map<LL,int>ib;structPersistent_Segment_Tree{structPoint{intl,r;LLsum;}p[N*......
  • 萌新的多项式学习笔记(板子)
    萌新的多项式学习笔记(板子)详细讲解FFT直接放板子structcp{ doublex,y; cp(doublexx=0,doubleyy=0){x=xx,y=yy;}};intr[maxn];cpoperator+(constcp&a,constcp&b){returncp(a.x+b.x,a.y+b.y);}cpoperator-(constcp&a,constcp&b){returncp(a.x-b.x,a......
  • 【板子】线性基
    //lgp3812#include<bits/stdc++.h>usingnamespacestd;#definellunsignedlonglonglld[100];intn;voidInsert(llx){ for(inti=62;i>=1;i--) { if(!(x>>(i-1)))continue; if(!d[i]) { d[i]=x; return; } else { ......
  • 【板子】后缀自动机(SAM)
    //lg3804//Copyrightyeyou26//注意:这道题不是纯纯的后缀自动机,main函数有一点额外处理#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineN(int(2e6+6))intfa[N];intch[N][28];intlen[N];intcnt[N];llans;intidx=1;intnp=1;str......
  • 【板子】冒泡/选择/插入 排序
    #include<bits/stdc++.h>usingnamespacestd;#defineN101inta[N];voidsort_mp(){for(inti=1;i<100;i++){for(intj=1;j<100;j++){if(a[j]>a[j+1]){swap(a[j],a[j+1]);......
  • 【板子】高斯约旦消元法(可判解)
    //lg2455#include<bits/stdc++.h>usingnamespacestd;constdoubleeps=0.000001;constintN=105;doublea[N][N];intn;intnowline=1;//存储当前行voidGaussJordan(){ for(inti=1;i<=n;i++)//枚举列若方程有唯一解则与枚举行列等效 { intmxline=no......
  • 【板子】快读/快写
    //double快读inlinevoidReadouble(double&ans){ ans=0; doubley=1.0; boolflag=0; charch=getchar(); while(!isdigit(ch)&&~ch) { flag|=(ch=='-'); ch=getchar(); } while(isdigit(ch)&&~ch) { ans=ans*10+(ch^48);......
  • 【板子】快速排序
    #include<bits/stdc++.h>usingnamespacestd;inta[114514];voidQuicksort(intl,intr);intmain(){freopen("working.in","r",stdin);freopen("working.out","w",stdout);intn;cin>>n;......
  • 【板子】归并排序
    #include<bits/stdc++.h>usingnamespacestd;constintN=1e6+6;intn;inta[N];intb[N];voidMergesort(intl,intr);longlongcnt;intmain(){freopen("working.in","r",stdin);freopen("working.out",&......