EK费用流求调,感谢
查看原帖
EK费用流求调,感谢
310726
Nagato_楼主2025/1/21 12:19

rt

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

#define int long long

const int N = 5010 , M = 100010 , INF = 1e15 ;

int h[N] , e[M] , f[M] , w[M] , ne[M] , idx;

void add(int u,int v,int ff,int ww)
{
    e[idx] = v , f[idx] = ff ,  w[idx] = ww , ne[idx] = h[u] , h[u] = idx++ ;
    e[idx] = u , f[idx] = 0 ,  w[idx] = -ww , ne[idx] = h[v] , h[v] = idx++ ;
}

int n,m,S,T;

queue<int> q;

int inq[N] , pre[N] , d[N] , v[N] ;

bool spfa()
{
    memset(d,0x3f,sizeof(d));
    
    q.push(S);
    inq[S] = 1 , d[S] = 0 , v[S] = INF , pre[S] = -1 ;
    while(!q.empty())
    {
        int p=q.front();
        q.pop();
        
        inq[p] = 0;
        for(int i=h[p];~i;i=ne[i])
        {
            int t=e[i];
            if( !f[i] || d[p] + w[i] >= d[t])
                continue;
            d[t] = d[p] + w[i];
            if(!inq[t])
            {
                inq[t] = 1 ;
                q.push(t);
            }
            v[t] = min(v[p],f[i]);
            pre[t] = i;
        }
    }
    return d[T]<=INF;
}

void SSP()
{
    int flow = 0 , cost = 0;
    
    while(spfa())
    {
        flow += v[T];
        for(int i=pre[T];~i;i=pre[e[pre[i]^1]])
            f[i] -= v[T] , cost += v[T]*w[i] , f[i^1] += v[T];
    }
    printf("%lld %lld",flow,cost);
}

signed main()
{
    memset(h,-1,sizeof(h));

    scanf("%lld%lld%lld%lld",&n,&m,&S,&T);

    for(int i=1,u,v,ff,ww;i<=m;i++)
    {
        scanf("%lld%lld%lld%lld",&u,&v,&ff,&ww);
        add(u,v,ff,ww);
    }

    SSP();

    return 0;
}
2025/1/21 12:19
加载中...