Advertisement
Guest User

Untitled

a guest
Nov 25th, 2015
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6. #include <queue>
  7. #include <set>
  8. #include <cstring>
  9. #include <map>
  10. #include <bitset>
  11. #include <random>
  12. #include <stack>
  13. #include <list>
  14.  
  15. using namespace std;
  16.  
  17. #define ll long long
  18. #define sc second
  19. #define fs first
  20. #define mp make_pair
  21. #define pb push_back
  22.  
  23. int c[1000][1000], f[1000][1000], n, p, k;
  24.  
  25. int main()
  26. {
  27. //FILE *f;
  28. //freopen_s(&f, "in.txt", "r", stdin);
  29. //freopen_s(&f, "out.txt", "w", stdout);
  30. freopen("input.in", "r", stdin);
  31. freopen("output.out", "w", stdout);
  32. cin >> n >> p >> k;
  33. for (int i = 1; i <= n; i++){
  34. for (int j = 1; j <= n; j++){
  35. cin >> c[i][j];
  36. }
  37. }
  38. int s = 0, fn = n + 1;
  39. for (int i = 0; i < p; i++){
  40. int v;
  41. cin >> v;
  42. c[s][v] = 1e9;
  43. }
  44. for (int i = 0; i < k; i++){
  45. int v;
  46. cin >> v;
  47. c[v][fn] = 1e9;
  48. }
  49. while (1)
  50. {
  51. int from[1000], q[1000], h = 0, t = 0;
  52. for (int i = 0; i < n + 2; i++)
  53. from[i] = -1;
  54. q[t++] = h;
  55. while (h < t){
  56. int cur = q[h++];
  57. for (int i = 0; i < n + 2; i++){
  58. if (from[i] == -1 && c[cur][i] - f[cur][i] > 0){
  59. from[i] = cur;
  60. q[t++] = i;
  61. }
  62. }
  63. }
  64. if (from[n + 1] == -1)
  65. break;
  66. int add = 1e9;
  67. for (int cur = n+1; cur != 0;){
  68. int prev = from[cur];
  69. add = min(add, c[prev][cur] - f[prev][cur]);
  70. cur = prev;
  71. }
  72. for (int cur = n+1; cur != 0;){
  73. int prev = from[cur];
  74. f[prev][cur] += add;
  75. cur = prev;
  76. }
  77. }
  78. int ans = 0;
  79. for (int i = 0; i < n+1; i++)
  80. ans += f[0][i];
  81. cout << ans;
  82. return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement