P3381 【模板】最小费用最大流

#include<cstdio>#include<cstring>#include<queue>#define pir pair<int,int>#define inf 0x33333333using namespace std;const int N=1e4+10;const int M=1e5+10;struct node{    int v,next,cap,cost;    node(int v=0,int next=0,int cap=0,int cost=0):v(v),next(next),cap(cap),cost(cost){}}e[M<<1];int tot=1;int n,m,S,T,head[N],pv[N],pe[N],dis[N],h[N];bool vis[N];void add(int x,int y,int cap,int cost){    e[++tot]=node(y,head[x],cap,cost);    head[x]=tot;}pir MCMF(){    int flow=0,cost=0;    while(1){        memset(dis,0x33,sizeof dis);        priority_queue<pir,vector<pir>,greater<pir> >q;        q.push(make_pair(dis[S]=0,S));        while(!q.empty()){            pir t=q.top();q.pop();            int x=t.second;            if(t.first!=dis[x]) continue;            if(x==T) break;            for(int i=head[x];i;i=e[i].next){                int v=e[i].v,newcost=e[i].cost+h[x]-h[v];                if(e[i].cap>0&&dis[v]>dis[x]+newcost){                    dis[v]=dis[x]+newcost;                    q.push(make_pair(dis[v],v));                    pv[v]=x;pe[v]=i;                }            }        }        if(dis[T]==inf) break;        for(int i=1;i<=n;i++) h[i]=min(h[i]+dis[i],inf);        int newflow=inf;        for(int i=T;i!=S;i=pv[i]){            newflow=min(newflow,e[pe[i]].cap);        }        flow+=newflow;        cost+=newflow*h[T];        for(int i=T;i!=S;i=pv[i]){            e[pe[i]].cap-=newflow;            e[pe[i]^1].cap+=newflow;        }    }    return make_pair(flow,cost);}int main(){    scanf("%d%d%d%d",&n,&m,&S,&T);    for(int i=1,x,y,z,w;i<=m;i++) scanf("%d%d%d%d",&x,&y,&z,&w),add(x,y,z,w),add(y,x,0,-w);    pir ans=MCMF();    printf("%d %d",ans.first,ans.second);    return 0;}

/*以费用作为权值，求出最小费用链，然后在这条链上求得一个最小流量，直到找不到费用链。求最小费用链也就相当于求src->des的最短路径。使用spfa+EK算法。得到MCMF算法*/#include<cstdio>#include<cstring>#include<queue>using namespace std;const int N=1e4+10;const int M=1e5+10;struct node{    int v,next,cap,flow,cost;    node(int v=0,int next=0,int cap=0,int flow=0,int cost=0):v(v),next(next),cap(cap),flow(flow),cost(cost){}}e[M<<1];int tot=1;int n,m,S,T,head[N],p[N],dis[N],num[N];bool vis[N];void add(int x,int y,int cap,int cost){    e[++tot]=node(y,head[x],cap,0,cost);    head[x]=tot;}bool spfa(int &flow,int &cost){    memset(vis,0,sizeof vis);    memset(dis,0x3f3f3f3f,sizeof dis);    queue<int>q;    q.push(S);    vis[S]=1;    dis[S]=0;    num[S]=0x7fffffff;    p[S]=0;    while(!q.empty()){        int x=q.front();q.pop();        vis[x]=0;        for(int i=head[x];i;i=e[i].next){            int v=e[i].v;            if(dis[v]>dis[x]+e[i].cost&&e[i].cap>e[i].flow){                dis[v]=dis[x]+e[i].cost;                p[v]=i;                num[v]=min(num[x],e[i].cap-e[i].flow);                if(!vis[v]){                    vis[v]=1;                    q.push(v);                }            }        }    }    if(dis[T]==0x3f3f3f3f) return 0;    flow+=num[T];    cost+=num[T]*dis[T];    for(int i=T;i!=S;i=e[p[i]^1].v){        e[p[i]].flow+=num[T];        e[p[i]^1].flow-=num[T];    }    return 1;}int main(){    scanf("%d%d%d%d",&n,&m,&S,&T);    for(int i=1,x,y,z,w;i<=m;i++) scanf("%d%d%d%d",&x,&y,&z,&w),add(x,y,z,w),add(y,x,0,-w);    int flow=0,cost=0;    while(spfa(flow,cost));    printf("%d %d\n",flow,cost);    return 0;}