#pragma region include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define dump(x) cerr << #x << " = " << (x) << " [" << __LINE__ << ":" << __FUNCTION__ << "] " << endl << flush // vector???��?��??��?��o???��?��??��?��???��?��??��?�� template < typename T > ostream& operator<<(ostream& os, vector< T >& v) { os << "{"; for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i < v.size() - 1 ? ", " : ""); } os << "}"; return os; } // pair???��?��??��?��o???��?��??��?��???��?��??��?�� template < typename T, typename U > ostream& operator<<(ostream& os, const pair< T, U >& p) { return os << "(" << p.first << ", " << p.second << ")"; } // map???��?��??��?��o???��?��??��?��???��?��??��?�� template < typename T, typename U > ostream& operator<<(ostream& os, const map< T, U >& map_var) { os << "{"; for (auto itr = map_var.begin(); itr != map_var.end(); itr++) { os << "(" << itr->first << ", " << itr->second << ")"; itr++; if (itr != map_var.end()) os << ", "; itr--; } os << "}"; return os; } // set ???��?��??��?��o???��?��??��?��???��?��??��?�� template < typename T > ostream& operator<<(ostream& os, const set< T >& set_var) { os << "{"; for (auto itr = set_var.begin(); itr != set_var.end(); itr++) { os << *itr; ++itr; if (itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } // multiset ???��?��??��?��o???��?��??��?��???��?��??��?�� template < typename T > ostream& operator<<(ostream& os, const multiset< T >& set_var) { os << "{"; for (auto itr = set_var.begin(); itr != set_var.end(); itr++) { os << *itr; ++itr; if (itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } #pragma endregion ///////////////////////////////////////// // 最大流O(V^2E) 実際もっと早い // 容量全部同じO(E√E) struct Dinic { private: struct edge { int to; ll cap; int rev; bool isrev; }; vector< vector< edge > > graph; vector< int > min_cost, iter; bool bfs(int s, int t) { min_cost.assign(graph.size(), -1); queue< int > que; min_cost[s] = 0; que.push(s); while (!que.empty() && min_cost[t] == -1) { int p = que.front(); que.pop(); for (auto &e : graph[p]) { if (e.cap == 0 || min_cost[e.to] != -1) continue; min_cost[e.to] = min_cost[p] + 1; que.push(e.to); } } return min_cost[t] != -1; } ll dfs(const int s, int v, ll flow) { if (v == s) return flow; ll res = 0; int min_cost_v = min_cost[v]; for (int &i = iter[v]; i < (int)graph[v].size(); i++) { edge &e = graph[v][i]; if (graph[e.to][e.rev].cap == 0 || min_cost_v <= min_cost[e.to]) continue; ll d = dfs(s, e.to, min(flow-res, graph[e.to][e.rev].cap)); if (d <= 0) continue; e.cap += d; graph[e.to][e.rev].cap -= d; res += d; if (res == flow) return res; } min_cost[v] = (int)graph.size(); return res; } public: Dinic() {} Dinic(int V) : graph(V) {} // from から to への容量capの有向辺 void add_edge(int from, int to, ll cap) { graph[from].push_back({to, cap, (int)graph[to].size(), false}); graph[to].push_back({from, 0, (int)graph[from].size() - 1, true}); } ll max_flow(int s, int t, ll flow_limit = 1e18 + 6) { ll flow = 0; while (bfs(s, t)) { if (min_cost[t] == -1) break; iter.assign(graph.size(), 0); ll f = dfs(s, t, flow_limit-flow); if (!f) break; flow += f; } return flow; } // 先にmax_flowが必要 // s側カットを出力 vector min_cnt(int s,int t) { vector visited(graph.size()); vector ret; stack sta; visited[s] = true; sta.push(s); ret.push_back(s); while(!sta.empty()) { int v = sta.top(); sta.pop(); for (auto &e : graph[v]) { if (visited[e.to] || e.cap == 0) continue; visited[e.to] = true; sta.push(e.to); ret.push_back(e.to); } } return ret; } void output() { for (int i = 0; i < graph.size(); i++) { for (auto &e : graph[i]) { if (e.isrev) continue; auto &rev_e = graph[e.to][e.rev]; cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl; } } } }; struct ProjectSelectionProblem { const long long INF = 1e18+1; // costには使わない int n; // 要素数 vector k; // 選択肢数 vector s; // 要素を表す頂点の開始index vector> cost; Dinic G; long long ans; // k:各要素の選択肢数 ProjectSelectionProblem(vector k) : k(k) { n = k.size(); s = vector(n+1); s[0] = 0; for (int i = 0; i < n; i++) { assert(k[i] >= 2); s[i+1] = s[i]+k[i]-1; } cost = vector>(n); for (int i = 0; i < n; i++) cost[i] = vector(k[i],0); G = Dinic(s[n]+2); ans = 0; } // aの選択のコスト void add_cost_1(int a,vector x) { assert(0 <= a && a < n); assert(k[a] == (int)x.size()); for (int i = 0; i < k[a]; i++) { cost[a][i] += x[i]; } } // x:abの選択間のコスト(Monge) void add_cost_2(int a,int b,vector> x) { assert(0 <= a && a < n && 0 <= b && b < n); assert((int)x.size() == k[a]); for (int i = 0; i < k[a]; i++) { assert((int)x[i].size() == k[b]); cost[a][i] += x[i][0]; for (int j = k[b]-1; j >= 0; j--) x[i][j] -= x[i][0]; } for (int i = 1; i < k[b]; i++){ cost[b][i] += x[k[a]-1][i]; for (int j = 0; j < k[a]; j++) x[j][i] -= x[k[a]-1][i]; } for (int i = 0; i < k[a]-1; i++){ for (int j = 0; j < k[b]-1; j++){ long long c = x[i+1][j]+x[i][j+1]-x[i][j]-x[i+1][j+1]; assert(c >= 0); if (c == 0) continue; G.add_edge(s[b]+j, s[a]+i, c); } } } long long mincost() { for (int i = 0; i < n; i++){ for (int j = 0; j < k[i]-2; j++) G.add_edge(s[i]+j+1, s[i]+j, INF); ans += cost[i][k[i]-1]; for (int j = 0; j < k[i]-1; j++){ if (cost[i][j] > cost[i][j+1]) { G.add_edge(s[n], s[i]+j, cost[i][j]-cost[i][j+1]); } else if (cost[i][j] < cost[i][j+1]) { G.add_edge(s[i]+j, s[n]+1, cost[i][j+1]-cost[i][j]); ans -= cost[i][j+1]-cost[i][j]; } } } return ans+G.max_flow(s[n], s[n]+1); } // 先にmincostが必要 // 選択した選択肢 vector answer() { vector ans(n); auto v = G.min_cnt(s[n],s[n]+1); vector scut(s[n]+2); for (int i = 0; i < v.size(); i++) scut[v[i]] = true; for (int i = 0; i < n; i++) { for (int j = 0; j < k[i]-1; j++) { if (!scut[s[i]+j]) { ans[i] = j; break; } else if (j == k[i]-2) { ans[i] = k[i]-1; } } } return ans; } }; int main() { int n,s,t;cin >> n >> s >> t; ProjectSelectionProblem psp(vector(n,2)); for (int i = 0; i < s; i++) { int e;cin >> e; e--; psp.add_cost_1(e,{0,(ll)1e18}); } for (int i = 0; i < t; i++) { int r;cin >> r; r--; psp.add_cost_1(r,{(ll)1e18,0}); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int c;cin >> c; if (i >= j) continue; psp.add_cost_2(i,j,{{-c,0},{0,-c}}); } } cout << -psp.mincost() << endl; return 0; } /////////////////////////////////////////