题解：P11879 [威海市赛2024] 速成之道

yedalong · 2026-03-05 14:07:31 · 题解

Solution

一个知识点可以选择有基础学、无基础学、不学。

故考虑从源点到汇点对于每一个知识点都有三条边，即将每一个知识点拆成两个点。

如果一个知识点是 X，一定要学，将其连向汇点，边权正无穷，意为不可不学。

假如知识点 u 被拆成了 u 和 u'。其中 s\rightarrow u 边权为有基础的，u\rightarrow u' 表示无基础的。

那么对于 u 的前置知识点 v，我们在割掉 s\rightarrow u 之前是得保证 v 已经学了，也就是说不可能出现没学 v 且没割 u\rightarrow u'。所以得保证 s\rightarrow v\rightarrow v' 和 u\rightarrow u' 中至少出现一条被割掉的边。如果不学 v，就只能选 u\rightarrow u' 了。

所以 u 的前置知识 v，我们 v'\rightarrow u，边权正无穷。

:::success[code]

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{int u,v,w;};
int n,m,s,t=201,u,v,d[205],flag[205];
vector<node> edges;
vector<int> e[205];
queue<int> q;
void add(int u,int v,int w){
    edges.push_back({u,v,w});
    edges.push_back({v,u,0});
    e[u].push_back(edges.size()-2);
    e[v].push_back(edges.size()-1);
}
bool bfs(){
    memset(d,0,sizeof d);
    while(!q.empty()) q.pop(); 
    d[s]=1,q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(auto to:e[u]){
            int v=edges[to].v;
            if(!d[v]&&edges[to].w){
                d[v]=d[u]+1;
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dfs(int u,int flow){
    if(u==t) return flow;
    int sum=0;
    for(int i = flag[u];i<e[u].size();i++){
        int v=edges[e[u][i]].v;
        if(edges[e[u][i]].w&&d[v]==d[u]+1){
            int tmp=dfs(v,min(flow,edges[e[u][i]].w));
            sum+=tmp,flow-=tmp,edges[e[u][i]].w-=tmp,edges[e[u][i]^1].w+=tmp;
            if(!flow) break;
        }
    }
    if(!sum) d[u]=-1;
    return sum;
}
int dinic(){
    int ans=0;
    while(bfs()){
        memset(flag,0,sizeof flag);
        ans+=dfs(s,1e18);
    }
    return ans;
}
signed main(){
    cin>>n>>m;
    for(int i = 1;i<=m;i++)
        cin>>u>>v,
        add(u+n,v,1e9);
    for(int i = 1;i<=n;i++)
        cin>>u,add(s,i,u);
    for(int i = 1;i<=n;i++)
        cin>>u,add(i,i+n,u);
    cin>>u;
    add(u+n,t,1e9);
    cout<<dinic();
    return 0;
}