Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <queue>
- #include <set>
- #include <cstring>
- #include <map>
- #include <bitset>
- #include <random>
- #include <stack>
- #include <list>
- using namespace std;
- #define ll long long
- #define sc second
- #define fs first
- #define mp make_pair
- #define pb push_back
- int c[1000][1000], f[1000][1000], n, p, k;
- int main()
- {
- //FILE *f;
- //freopen_s(&f, "in.txt", "r", stdin);
- //freopen_s(&f, "out.txt", "w", stdout);
- freopen("input.in", "r", stdin);
- freopen("output.out", "w", stdout);
- cin >> n >> p >> k;
- for (int i = 1; i <= n; i++){
- for (int j = 1; j <= n; j++){
- cin >> c[i][j];
- }
- }
- int s = 0, fn = n + 1;
- for (int i = 0; i < p; i++){
- int v;
- cin >> v;
- c[s][v] = 1e9;
- }
- for (int i = 0; i < k; i++){
- int v;
- cin >> v;
- c[v][fn] = 1e9;
- }
- while (1)
- {
- int from[1000], q[1000], h = 0, t = 0;
- for (int i = 0; i < n + 2; i++)
- from[i] = -1;
- q[t++] = h;
- while (h < t){
- int cur = q[h++];
- for (int i = 0; i < n + 2; i++){
- if (from[i] == -1 && c[cur][i] - f[cur][i] > 0){
- from[i] = cur;
- q[t++] = i;
- }
- }
- }
- if (from[n + 1] == -1)
- break;
- int add = 1e9;
- for (int cur = n+1; cur != 0;){
- int prev = from[cur];
- add = min(add, c[prev][cur] - f[prev][cur]);
- cur = prev;
- }
- for (int cur = n+1; cur != 0;){
- int prev = from[cur];
- f[prev][cur] += add;
- cur = prev;
- }
- }
- int ans = 0;
- for (int i = 0; i < n+1; i++)
- ans += f[0][i];
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement