この問題は最大流問題そのものです。

次のようなグラフを用意します。

• \(K\) 個の発電所・ \(N\) 個の工場及び、2つの頂点 \(X,Y\) からなる \(N+K+2\) 頂点
• \(X\) から各発電所 \(i\) へ、容量 \(W_i\) の辺
• 各工場 \(i\) から \(Y\) へ、容量 \(B_i\) の辺
• 与えられた \(M\) 本の送電線に対応する、 2 頂点を結ぶ容量 \(C_i\) の無向辺（双方向に有向辺を張れば良い）

このグラフにおける、頂点 \(X\) から頂点 \(Y\) への最大流が、 \(\sum B_i\) に一致していることが、答えが Yes であるための必要十分条件になります。（ \(X\) 及び \(Y\) がそれぞれ”供給”と”需要”を一括に管理する頂点であることをイメージすると、同値性は明らかです）

このグラフは頂点数 \(N+K+2\) 、辺数 \(M+N+K\) であることから、最大流を求めることは、 Dinic 法により \(O((N+K)^2(M+N+K))\) でできます。よってこれを愚直に \(Q\) 回繰り返すことでこの問題を解くことができます。

最大流を求めるライブラリが AtCoder Library として提供されており、 AtCoder 上で利用可能です。

なお、発電所から工場の方向へフローを流すのか、工場から発電所の方向へフローを流すのかは、有向辺の向きさえ正しく定めればどちらでも同じになるため、以下の実装例では上述べたグラフとは逆に、工場から発電所の方向へフローを流しています。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/maxflow>
using namespace std;

int main(){
  int n, k, m;
  cin >> n >> k >> m;
  vector<int>b(n),w(k);
  for(int i=0; i<n; i++) cin >> b[i];
  for(int i=0; i<k; i++) cin >> w[i];
  vector<array<int,3>>e(m);
  for(int i=0; i<m; i++){
    int u, v, c;
    cin >> u >> v >> c;
    u--, v--;
    e[i] = {u, v, c};
  }
  
  long long required = 0;
  for(int i=0; i<n; i++) required += b[i];
  
  int q;
  cin >> q;
  vector<bool>ok(k, true);
  while(q--){
    int s;
    cin >> s;
    s--;
    ok[s] = false;
    
    // n+k - (0 ~ n-1) - (n ~ n+k-1) - n+k+1
    atcoder::mf_graph<long long>g(n+k+2);
    for(auto[u, v, c]: e){
      g.add_edge(u, v, c);
      g.add_edge(v, u, c);
    }
    for(int i=0; i<n; i++){
      g.add_edge(n+k, i, b[i]);
    }
    for(int i=0; i<k; i++){
      if(ok[i]){
        g.add_edge(n+i, n+k+1, w[i]);
      }
    }
    long long flow = g.flow(n+k, n+k+1);
    if(flow == required){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }
}

実装例 (Python)

from atcoder.maxflow import MFGraph

N, K, M = map(int, input().split())
B = list(map(int, input().split()))
W = list(map(int, input().split()))
E = []
for _ in range(M):
  U, V, C = list(map(int, input().split()))
  U -= 1
  V -= 1
  E.append((U, V, C))

required = sum(B)

ok = [True] * K
Q = int(input())
for _ in range(Q):
  S = int(input())
  S -= 1
  ok[S] = False
  
  G = MFGraph(N+K+2)
  for u, v, c in E:
    G.add_edge(u, v, c)
    G.add_edge(v, u, c)
  for i in range(N):
    G.add_edge(N+K, i, B[i])
  for i in range(K):
    if ok[i]:
      G.add_edge(N+i, N+K+1, W[i])
  flow = G.flow(N+K, N+K+1)
  if flow == required:
    print("Yes")
  else:
    print("No")