【BZOJ】1834 [ZJOI2010]network 网络扩容

时间：2023-03-08 16:59:25
【BZOJ】1834 [ZJOI2010]network 网络扩容

【算法】网络流-最大流+最小费用最大流(费用流)

【题解】

第一问跑最大流。

第二问：

原始边相当于费用为0的边，再原图(跑过最大流的图)基础上添加带费用的边，容量为k(相当于inf)。

第一问最大流使用了哪条边对第二问没有影响，因为费用流肯定优先往费用为0的边(原始边)跑。

限流k？添加超级源向1连容量k费用0的边即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=,maxm=,N=,inf=0x3f3f3f3f;

int tot=,first[maxn],d[maxn],q[maxn],cur[maxn],S,T,sum,n,m,K,u[maxm],v[maxm],w[maxm];

bool vis[maxn];

struct edge{int v,f,c,from;}e[maxm*];

void insert(int u,int v,int f,int c){

    tot++;e[tot].v=v;e[tot].f=f;e[tot].c=c;e[tot].from=first[u];first[u]=tot;

    tot++;e[tot].v=u;e[tot].f=;e[tot].c=-c;e[tot].from=first[v];first[v]=tot;

}

bool bfs(){

    memset(d,-,sizeof(d));

    int head=,tail=;q[head]=S;d[S]=;

    while(head<tail){

        int x=q[head++];

        for(int i=first[x];i;i=e[i].from)

        if(e[i].f&&d[e[i].v]==-){

            d[e[i].v]=d[x]+;

            q[tail++]=e[i].v;

        }

    }

    return ~d[T];

}

int dinic(int x,int a){

    if(x==T||a==)return a;

    int flow=,f;

    for(int& i=cur[x];i;i=e[i].from)

    if(d[e[i].v]==d[x]+&&(f=dinic(e[i].v,min(e[i].f,a)))){

        e[i].f-=f;e[i^].f+=f;

        flow+=f;a-=f;

        if(a==)break;

    }

    return flow;

}

int solve1(){

    int ans=;

    while(bfs()){

        for(int i=S;i<=T;i++)cur[i]=first[i];

        ans+=dinic(S,inf);

    }

    return ans;

}

bool spfa(){

    memset(d,0x3f,sizeof(d));

    int head=,tail=;q[head]=T;d[T]=;vis[T]=;

    while(head!=tail){

        int x=q[head++];if(head>N)head=;

        for(int i=first[x];i;i=e[i].from)

        if(e[i^].f&&d[x]+e[i^].c<d[e[i].v]){

            d[e[i].v]=d[x]+e[i^].c;

            if(!vis[e[i].v]){

                if(d[e[i].v]<d[q[head]]){if(--head<)head=N;q[head]=e[i].v;}

                else{q[tail++]=e[i].v;if(tail>N)tail=;}

                vis[e[i].v]=;

            }

        }

        vis[x]=;//

    }

    return d[S]<inf;

}

int dfs(int x,int a){

    if(x==T||a==)return a;

    vis[x]=;

    int flow=,f;

    for(int& i=cur[x];i;i=e[i].from)

    if(!vis[e[i].v]&&d[e[i].v]+e[i].c==d[x]&&(f=dfs(e[i].v,min(e[i].f,a)))){

        e[i].f-=f;e[i^].f+=f;

        sum+=e[i].c*f;

        flow+=f;a-=f;

        if(a==)break;

    }

    vis[x]=;

    return flow;

}

int solve2(){

    sum=;

    while(spfa()){

        for(int i=S;i<=T;i++)cur[i]=first[i];

        dfs(S,inf);

    }

    return sum;

}

int main(){

    scanf("%d%d%d",&n,&m,&K);

    S=;T=n;

    for(int i=;i<=m;i++){

        int c;

        scanf("%d%d%d%d",&u[i],&v[i],&c,&w[i]);

        insert(u[i],v[i],c,);

    }

    printf("%d ",solve1());

    S=;

    for(int i=;i<=m;i++)insert(u[i],v[i],K,w[i]);

    insert(S,,K,);

    printf("%d",solve2());

    return ;

}
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=,maxm=,N=,inf=0x3f3f3f3f;

int tot=,first[maxn],d[maxn],q[maxn],cur[maxn],S,T,sum,n,m,K,u[maxm],v[maxm],w[maxm],c[maxm];

bool vis[maxn];

struct edge{int v,f,c,from;}e[maxm*];

void insert(int u,int v,int f,int c){

    tot++;e[tot].v=v;e[tot].f=f;e[tot].c=c;e[tot].from=first[u];first[u]=tot;

    tot++;e[tot].v=u;e[tot].f=;e[tot].c=-c;e[tot].from=first[v];first[v]=tot;

}

bool bfs(){

    memset(d,-,sizeof(d));

    int head=,tail=;q[head]=S;d[S]=;

    while(head<tail){

        int x=q[head++];

        for(int i=first[x];i;i=e[i].from)

        if(e[i].f&&d[e[i].v]==-){

            d[e[i].v]=d[x]+;

            q[tail++]=e[i].v;

        }

    }

    return ~d[T];

}

int dinic(int x,int a){

    if(x==T||a==)return a;

    int flow=,f;

    for(int& i=cur[x];i;i=e[i].from)

    if(d[e[i].v]==d[x]+&&(f=dinic(e[i].v,min(e[i].f,a)))){

        e[i].f-=f;e[i^].f+=f;

        flow+=f;a-=f;

        if(a==)break;

    }

    return flow;

}

int solve1(){

    int ans=;

    while(bfs()){

        for(int i=S;i<=T;i++)cur[i]=first[i];

        ans+=dinic(S,inf);

    }

    return ans;

}

bool spfa(){

    memset(d,0x3f,sizeof(d));

    int head=,tail=;q[head]=T;d[T]=;vis[T]=;

    while(head!=tail){

        int x=q[head++];if(head>N)head=;

        for(int i=first[x];i;i=e[i].from)

        if(e[i^].f&&d[x]+e[i^].c<d[e[i].v]){

            d[e[i].v]=d[x]+e[i^].c;

            if(!vis[e[i].v]){

                if(d[e[i].v]<d[q[head]]){if(--head<)head=N;q[head]=e[i].v;}

                else{q[tail++]=e[i].v;if(tail>N)tail=;}

                vis[e[i].v]=;

            }

        }

        vis[x]=;//

    }

    return d[S]<inf;

}

int dfs(int x,int a){

    if(x==T||a==)return a;

    vis[x]=;

    int flow=,f;

    for(int& i=cur[x];i;i=e[i].from)

    if(!vis[e[i].v]&&d[e[i].v]+e[i].c==d[x]&&(f=dfs(e[i].v,min(e[i].f,a)))){

        e[i].f-=f;e[i^].f+=f;

        sum+=e[i].c*f;

        flow+=f;a-=f;

        if(a==)break;

    }

    vis[x]=;

    return flow;

}

int solve2(){

    sum=;

    while(spfa()){

        for(int i=S;i<=T;i++)cur[i]=first[i];

        dfs(S,inf);

    }

    return sum;

}

int main(){

    scanf("%d%d%d",&n,&m,&K);

    S=;T=n;

    for(int i=;i<=m;i++){

        scanf("%d%d%d%d",&u[i],&v[i],&c[i],&w[i]);

        insert(u[i],v[i],c[i],);

    }

    int now=;

    printf("%d ",now=solve1());

    tot=;memset(first,,sizeof(first));//

    for(int i=;i<=m;i++){

        insert(u[i],v[i],c[i],);

        insert(u[i],v[i],K,w[i]);

    }

    S=;

    insert(S,,now+K,);

    printf("%d",solve2());

    return ;

}

相关文章