dinic费用流MLE求助
查看原帖
dinic费用流MLE求助
513900
Wilson_Lee楼主2022/10/17 22:03
#include<bits/stdc++.h>
using namespace std;

const int MAXN=5e3+5;
const int MAXM=1e5+5;
const int INF=1e8;
struct EDGE
{
    int to,nxt,flow,cost;
}edge[MAXM];
int head[MAXN],tot=1;
int dis[MAXN],now[MAXN];
bool vis[MAXN];
int n,m,s,t;
int maxflow,mincost;
queue<int>q;
void add(int x,int y,int z,int c)
{
    edge[++tot]=(EDGE){y,head[x],z,c},head[x]=tot;
    edge[++tot]=(EDGE){x,head[y],0,-c},head[y]=tot;
}
bool spfa()
{
    while(!q.empty()) q.pop();
    memset(dis,0x3f,sizeof(dis));
    q.push(s),dis[s]=0,vis[s]=1,now[s]=head[s];
    while(!q.empty())
    {
        int x=q.front();q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=edge[i].nxt)
        {
            int y=edge[i].to,z=edge[i].flow,c=edge[i].cost;
            if(dis[y]>dis[x]+c && z)
            {
                dis[y]=dis[x]+c,now[y]=head[y];
                if(!vis[y]) q.push(y),vis[y]=1;
            }
        }
    }
    return dis[t]!=dis[0];
}
int dinic(int x,int flow)
{
    if(x==t) return flow;
    vis[x]=1;
    int incf=0;
    for(int i=now[x];i;i=edge[i].nxt)
    {
        now[x]=i;
        int y=edge[i].to,z=edge[i].flow,c=edge[i].cost;
        if(dis[y]==dis[x]+c && z)
        {
            int tmp=dinic(y,min(flow-incf,z));
            if(tmp) edge[i].flow-=tmp,edge[i^1].flow+=tmp,incf+=tmp,mincost+=tmp*c;
            else dis[y]=INF;
            if(incf==flow) break;
        }
    }
    vis[x]=0;
    return incf;
}
int main()
{
    cin>>n>>m>>s>>t;
    int u,v,w,c;
    for(int i=1;i<=m;++i) scanf("%d %d %d %d",&u,&v,&w,&c),add(u,v,w,c);
    while(spfa()) maxflow+=dinic(s,INF);
    cout<<maxflow<<" "<<mincost;
    return 0;
}
2022/10/17 22:03
加载中...