P11531 [THUPC2025 初赛] 检查站 题解

· · 题解

P11531 [THUPC2025 初赛] 检查站 题解

鲜花：考场上两名队友在开考 2h 时开始死磕这道题，磕到最后一无所有，本人当时太菜，没学网络流，今重新读题做题，25min 切掉了本题，不知道考场上他俩在想什么。

思路

注意到问题可以看成最小割模型，即通过花费一定的代价割掉一些边，把点集分成两个不相交的子集，令 1 号节点和 n 号节点分别处于不同的两个部分，求最少需要的花费。

考虑建模，题目要求的是把分部割掉，并花费 1 的代价，所以我们考虑把分部拆成两个节点，一个节点只负责接入边，另一个节点只负责接出边。对于第 i 个分部，我们称其直接入边的节点叫做 I_i，只接出边的节点叫做 O_i，并连接一条 I_i\to O_i 且容量为 1 的边。

对于题面当中的一条铁轨来说，我们这样进行连边：

然后在这个网络图上跑 Dinic 就可以了。

建模正确性论证

我们来论证一下上述建模方法的正确性，简单地说，我们希望找到一种建模方式，使得删掉一个分部之后，所有由该分部控制的铁轨都断掉，并且该建模方式不影响原图的连通性。

采用上述建模方式，第一点要求是显然能够满足的，因为割掉 I_i\to O_i 这条边后，所有由 i 控制的铁路肯定都断了。考虑第二点要求，由于题目当中说 p_r=u 或者 p_r=v 必然满足其一，所以可能产生的不在原图中的铁轨有且仅有 p\to p 这种环，但是这种环显然对连通性没有任何影响，所以直接这么建模就是对的。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#define ll int
using namespace std;
const ll N=2e5+10;
const ll M=N<<2;
const ll INF=2147483647;
struct node{ll v,S,nxt;}e[M];
ll head[N],tot=1;
void add_edge(ll from,ll to,ll C){
    e[++tot]={to,C,head[from]};
    head[from]=tot;
}
//1~n station
//n+1~n+c part_in
//n+c+1~n+2c part_out 
ll n,m,c,pt=n,pls[N],S,T;
ll cur[N],dep[N];
bool bfs(){
    for(ll i=1;i<=n+2*c;i++) dep[i]=0;
    queue<ll> qu;
    qu.push(S);dep[S]=1;
    while(!qu.empty()){
        ll v,now=qu.front();qu.pop();
        for(ll i=head[now];i;i=e[i].nxt){
            v=e[i].v;
            if(dep[v]||!e[i].S) continue;
            dep[v]=dep[now]+1;
            if(v==T) return 1;
            qu.push(v);
        }
    }
    return 0;
}
inline ll dfs(ll now,ll MX){
    if(T==now) return MX;
    ll sum=0,linO,v;
    for(ll i=cur[now];i;i=e[i].nxt){
        cur[now]=i;v=e[i].v;
        if(dep[v]!=dep[now]+1||!e[i].S) continue;
        linO=dfs(v,min(MX,e[i].S));
        e[i].S-=linO,e[i^1].S+=linO;
        MX-=linO,sum+=linO;
        if(!MX) break; 
    }
    if(!sum) dep[now]=0;
    return sum;
}
ll Dinic(){
    ll ret=0;
    while(bfs()){
        for(ll i=1;i<=n+2*c;i++) cur[i]=head[i];
        ret+=dfs(S,INF);
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>c;
    S=1,T=n;
    for(ll i=n+1;i<=n+c;i++) add_edge(i,i+c,1),add_edge(i+c,i,0);
    for(ll i=1;i<=c;i++) cin>>pls[i];
    for(ll i=1;i<=m;i++){
        ll u,v,r;
        cin>>u>>v>>r;
        add_edge(u,r+n,INF);add_edge(r+n,u,0);
        add_edge(n+c+r,v,INF);add_edge(v,n+c+r,0);
    }
    cout<<Dinic();
    return 0;
}