题解-CF708D Incorrect Flow

题面

CF708D Incorrect Flow

给一张网络流图，可能有流量不守恒或者流量超过容量的情况，求最少的将某条边流量或容量 \(\pm 1\) 的操作次数使得网络流图正确。

数据范围：\(1\le n,m\le 100\)，\(0\le f,c\le 10^6\)。

题解

是一篇由思考题目时的笔记修改成的题解，希望不同的思考轨迹可以帮助仍然有能力学习 OI 的您。

设 \(d(u)\) 为当前 \(u\) 节点 出流 \(-\) 入流，要让所有 \(d(u)=0\)。

如何解决 \(d(s)\) 和 \(d(t)\)？可以想象一条 \((t,s,F,\infty)\) 的原边，\(F\) 待定，要使答案最优。

如果原边 \((u,v,f,c)\) 变成 \((u,v,f-1,c)\)，\(d(u)\) 减少 \(1\)，\(d(v)\) 增加 \(1\)；\((u,v,f,c)\) 变成 \((u,v,f+1,c)\) 亦然。

然后建立真正的源点 \(S\) 和汇点 \(T\)。

所以如果 \(d(u)>0\) 连 \((S,u,d(u),0)\)，如果 \(d(u)<0\) 连 \((u,T,-d(u),0)\)。

这样可以转化为一个把 \(d(u)>0\) 的施舍给 \(d(u)<0\) 的问题。

这里先说一个明显的东西：\(c\) 是不需要减的。

对于原边 \((u,v,f)\)，@如果 \(f\le c\)，连 \((u,v,f,1)\)（\(f\) 减小）和 \((v,u,c-f,1)\)（\(f\) 增加），表示不影响容量改变流量的施舍。

再加上 \((v,u,\infty,2)\)，因为当 \(f=c\) 以后可以一起增加 \(\infty\) 次。

@如果 \(c<f\)，答案操作次数至少加 \(f-c\)。

先把 \(f\) 减成 \(c\)，答案操作次数先加 \(f-c\)。

在 \(f-c\) 次限度内，\(f\) 增加的消耗可以用 \(c\) 当时少减少抵消。

所以连边 \((u,v,c,1)\)（\(f\) 减小）和 \((v,u,f-c,0)\)（\(f\) 增加）。

同样要连 \((v,u,\infty,2)\)，因为 \(c=f\) 以后可以一起增加 \(\infty\) 次。

最后回来定 \(F\)：很明显 \(F\) 应该是非负整数，不如先当成 \(0\) 算出 \(d(s),d(t)\)，然后连 \((t,s,\infty,0)\)，表示这是条免费增加的边。

然后 当前答案操作次数 \(+\) 最大流最小费用 就是答案。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef double db;

#define x first

#define y second

#define bg begin()

#define ed end()

#define pb push_back

#define mp make_pair

#define sz(a) int((a).size())

#define R(i,n) for(int i(0);i<(n);++i)

#define L(i,n) for(int i((n)-1);~i;--i)

const int iinf=0x3f3f3f3f;

const ll linf=0x3f3f3f3f3f3f3f3f;

//Data

const int N=100;

int n,m,d[N];

//Flows

const int fN=N+2;

int fn,s,t;

vector<int> e[fN],to,fw,co;

void adde(int u,int v,int w,int c){

    // cout<<u<<' '<<v<<' '<<w<<' '<<c<<'\n';

    e[u].pb(sz(to)),to.pb(v),fw.pb(w),co.pb(+c);

    e[v].pb(sz(to)),to.pb(u),fw.pb(0),co.pb(-c);

}

int dep[fN],pre[fN]; bool vis[fN]; queue<int> q;

bool spfa(){

    R(u,fn) dep[u]=iinf,pre[u]=-1,vis[u]=false;

    q.push(pre[s]=s),dep[s]=0,vis[s]=true;

    while(sz(q)){

        int u=q.front(); q.pop(),vis[u]=false;

        for(int v:e[u])if(fw[v]&&dep[to[v]]>dep[u]+co[v])

            dep[to[v]]=dep[u]+co[v],pre[to[v]]=v,

            !vis[to[v]]&&(q.push(to[v]),vis[to[v]]=true);

    }

    return dep[t]^iinf;

}

pair<int,int> flow(){

    pair<int,int> res(0,0);

    while(spfa()){

        int f=iinf;

        for(int u=t;u^s;u=to[pre[u]^1]) f=min(f,fw[pre[u]]);

        for(int u=t;u^s;u=to[pre[u]^1]) fw[pre[u]]-=f,fw[pre[u]^1]+=f;

        res.x+=f,res.y+=dep[t]*f;

    }

    return res;

}

//Main

int main(){

    ios::sync_with_stdio(0);

    cin.tie(0),cout.tie(0);

    cin>>n>>m,fn=(t=(s=n)+1)+1;

    int sm=0; adde(0,n-1,iinf,0);

    R(i,m){

        int u,v,w,c; cin>>u>>v>>c>>w,--u,--v;

        if(w<=c) adde(u,v,w,1),adde(v,u,c-w,1);

        else sm+=w-c,adde(u,v,c,1),adde(u,v,w-c,0);

        d[u]+=w,d[v]-=w,adde(v,u,iinf,2);

    }

    R(u,n)if(d[u]>0) adde(s,u,d[u],0);

        else adde(u,t,-d[u],0);

    cout<<sm+flow().y<<'\n';

    return 0;

}

祝大家学习愉快！

巴特西

题解-CF708D Incorrect Flow

题面

题解

代码

最新文章

热门文章