[ZJOI2010] 网络扩容

题意

给定一张有向图,每条边都有容量 和扩容费用 。这里扩容费用指将容量扩大 1 所需的费用。求:

  1. 在不扩容的情况下,1 到 N 的最大流.
  2. 将 1 到 N 的最大流增加 K 所需的最小扩容费用.

Subtask1

EK 或者 Dinic 跑一遍最大流,建图的时候把费用设成 0.

Subtask2

在 Subtask1 的残存网络的基础上,给每条边建一个副本,只是把容量改成 INF,费用为 .

还要求最大流只增加 K,那就再建一个源点连接 1 号点,容量设成 K,费用为 0,这就限制了流量

那么跑最小费用最大流就行

代码

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e4,M=1e5,INF=0x3f3f3f3f;
int n,m,k,s,t;

struct qxx{int nex,t,v,c;};
qxx e[M];
int h[N],cnt=1;
void add_path(int f,int t,int v,int c){e[++cnt]=(qxx){h[f],t,v,c},h[f]=cnt;}
void add_flow(int f,int t,int v,int c){add_path(f,t,v,c),add_path(t,f,0,-c);}

int dis[N],pre[N],incf[N];
bool vis[N];
bool spfa(){memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(s),dis[s]=0,incf[s]=INF,incf[t]=0;
    while(q.size()){int u=q.front();q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v,&c=e[i].c;
            if(!w||dis[v]<=dis[u]+c)continue;
            dis[v]=dis[u]+c,incf[v]=min(w,incf[u]),pre[v]=i;
            if(!vis[v])q.push(v),vis[v]=1;
        }
    }
    return incf[t];
}
int maxflow,mincost;
void update(){maxflow+=incf[t];
    for(int u=t;u!=s;u=e[pre[u]^1].t){e[pre[u]].v-=incf[t],e[pre[u]^1].v+=incf[t];
        mincost+=incf[t]*e[pre[u]].c;
    }
}
int u[M],v[M],c[M],w[M];
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)scanf("%d%d%d%d",&u[i],&v[i],&c[i],&w[i]),add_flow(u[i],v[i],c[i],0);
    s=1,t=n;
    while(spfa())update();
    printf("%d",maxflow);//sbt1
    for(int i=1;i<=m;i++)add_flow(u[i],v[i],INF,w[i]);
    s=0,add_flow(s,1,k,0);
    while(spfa())update();
    printf("%d",mincost);//sbt2
    return 0;
}

  转载请注明: Sshwy's Blog [ZJOI2010] 网络扩容

 上一篇
[SCOI2010] 连续攻击游戏 [SCOI2010] 连续攻击游戏
题意游戏里有很多的装备,每种装备都有 2 个属性,属性值为 [1,10000] 之间的数。 使用某种装备只能使用该装备的一个属性。每种装备最多只能使用一次。 要求使用的装备的属性值从 1 开始连续递增,想知道他最多能连续攻击多少次? 分析
2019.01.14
下一篇 
[CQOI2012] 交换棋子 [CQOI2012] 交换棋子
题意有一个 n 行 m 列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第 i 行第 j 列的格子只能参与 次交换。 求最小交换总次数。如果无解,输出 -1。 分析非
2019.01.14
  目录