题解归档 - cf362E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf362E
• 本地来源：problems/cf362E/idea.md
• 题目链接：https://codeforces.com/contest/362/problem/E
• 原始标题：362E Petya and Pipes

思路

362E Petya and Pipes

题意

(n) 个水箱，矩阵 (c_{ij}) 为 (i\to j) 管道容量（0 表示无管道）。总预算 (k)，可给若干管道各增加整数宽度，总增量 (\le k)。求 (1\to n) 最大流。

思路

每条原管道拆两条弧：

• 容量 (c_{ij})，费用 0（原有宽度）
• 容量 (\infty)，费用 1（每扩 1 单位宽度耗 1 预算）

最小费用最大流：SPFA 找最短路增广；当最短路费用 (>0) 时，增广量受剩余预算限制 (\lfloor (k-\text{spent})/\text{dist}\rfloor)。

模板

lib/图论(Dinic最大流).cpp — 含 Dinic 与最小费用最大流（SPFA）。

验证

样例 8 / 10 / 5 ✅

结果

• CF #377694628 — AC
• 模板：lib/图论(Dinic最大流).cpp

代码

来源：problems/cf362E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:20:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=55,INF=1e18;
struct edge{ll to,cap,cost,rev;};
vector<edge>g[maxn];
ll n,k,i,j,u,v,c,flow,s,t,budget;
ll d[maxn],p[maxn],pe[maxn],inq[maxn];
void add(ll a,ll b,ll cap,ll cost){
    g[a].push_back({b,cap,cost,(ll)g[b].size()});
    g[b].push_back({a,0,-cost,(ll)g[a].size()-1});
}
bool spfa(){
    ll i,h=0,tl=1,q[maxn+5];
    for(i=1;i<=n;i++) d[i]=INF,inq[i]=0;
    d[s]=0,q[0]=s,inq[s]=1;
    while(h!=tl){
        u=q[h++];if(h==maxn+1) h=0;
        inq[u]=0;
        for(i=0;i<(ll)g[u].size();i++){
            edge e=g[u][i];
            if(e.cap>0 and d[u]+e.cost<d[e.to]){
                d[e.to]=d[u]+e.cost;
                p[e.to]=u,pe[e.to]=i;
                if(!inq[e.to]){
                    q[tl++]=e.to,inq[e.to]=1;
                    if(tl==maxn+1) tl=0;
                }
            }
        }
    }
    return d[t]!=INF;
}
ll mcmf(){
    ll ans=0,spent=0;
    while(spfa()){
        ll aug=INF;
        for(v=t;v!=s;v=p[v]) aug=min(aug,g[p[v]][pe[v]].cap);
        if(d[t]>0) aug=min(aug,(budget-spent)/d[t]);
        if(aug<=0) break;
        for(v=t;v!=s;v=p[v]){
            edge &e=g[p[v]][pe[v]];
            e.cap-=aug;
            g[v][e.rev].cap+=aug;
        }
        spent+=d[t]*aug;
        ans+=aug;
    }
    return ans;
}
int main(){
    cin>>n>>k;
    budget=k,s=1,t=n;
    for(i=1;i<=n;i++) for(j=1;j<=n;j++){
        cin>>c;
        if(c>0){
            add(i,j,c,0);
            add(i,j,INF,1);
        }
    }
    cout<<mcmf()<<"\n";
    return 0;
}