题解：P2936 [USACO09JAN] Total Flow S

qianyuzhe · 2026-07-26 17:13:12 · 题解

为什么题解区全是网络流？这让我怎么打银组？

注意到这张图有特殊性质，所以实际上我们可以不用网络流做到线性。

根据题目描述，我们考虑使用广义串并联图方法求解。

::::info[如果你不会广义串并联图] 广义串并联图的定义就是题目中“测试数据中的所有网络都可以使用这里的规则简化”这句话。

对于任意一个广义串并联图，可以通过以下三种操作将其缩成一个点：

• 删一度点‌：把只连了一条边的点连同边直接删掉。
• 缩二度点‌：把连了两条边的点去掉，把它连的两条边合并成一条新边。
• 叠合重边‌：把两个点之间多条相同的边合并成一条。

在本题中，我们不需要把其缩成一个点，所以我们永远不对 A 和 Z 进行操作，这样就可以把原图变成一条连接 A 和 Z 的边。 ::::

分类讨论：

• 删一度点。直接删即可。
• 缩二度点。将新边权值设为原两边权值的最小值。
• 叠合重边。将新边权值设为原两边权值的和。

::::success[code]{open}

#include<bits/stdc++.h>
#define link(x,y,z) e[x][y]=e[y][x]+=z
using namespace std;
int n,m,f,i;
char a,b;
queue<int>q;
unordered_map<int,int>e[53];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    for(cin>>n;n--;link(isupper(a)?a-64:a-70,isupper(b)?b-64:b-70,f))cin>>a>>b>>f;
    for(i=2;i<53;i++)if(i!=26&&e[i].size()<3)q.push(i);
    for(;q.size();q.pop()){
        vector<pair<int,int> >v(e[q.front()].begin(),e[q.front()].end());
        if(v.size()==2)link(v[0].first,v[1].first,min(v[0].second,v[1].second));
        for(auto i:v)e[i.first].erase(q.front());
        e[q.front()].clear();
        for(auto i:v)if(i.first>1&&i.first!=26&&e[i.first].size()<3)q.push(i.first);
    }
    cout<<e[1].begin()->second;
}

::::

很简单吧！！！