fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int MAXN = 500;
  5. int g[MAXN][MAXN];
  6. int best_cost = 1000000000;
  7.  
  8. void mincut(int n) {
  9. 	vector<int> v[MAXN];
  10. 	for (int i=0; i<n; ++i)
  11. 		v[i].assign (1, i);
  12. 	int w[MAXN];
  13. 	bool exist[MAXN], in_a[MAXN];
  14. 	for (auto &e:exist){
  15. 		e = true;
  16. 	}
  17. 	for (int ph=0; ph<n-1; ++ph) {
  18. 		for (auto &e:in_a){
  19. 			e = false;
  20. 		}
  21. 		for (auto &e:w){
  22. 			e = 0;
  23. 		}
  24. 		for (int it=0, prev; it<n-ph; ++it) {
  25. 			int sel = -1;
  26. 			for (int i=0; i<n; ++i)
  27. 				if (exist[i] && !in_a[i] && (sel == -1 || w[i] > w[sel]))
  28. 					sel = i;
  29. 			if (it == n-ph-1) {
  30. 				if (w[sel] < best_cost)
  31. 					best_cost = w[sel];
  32. 				v[prev].insert (v[prev].end(), v[sel].begin(), v[sel].end());
  33. 				for (int i=0; i<n; ++i)
  34. 					g[prev][i] = g[i][prev] += g[sel][i];
  35. 				exist[sel] = false;
  36. 			}
  37. 			else {
  38. 				in_a[sel] = true;
  39. 				for (int i=0; i<n; ++i)
  40. 					w[i] += g[sel][i];
  41. 				prev = sel;
  42. 			}
  43. 		}
  44. 	}
  45. }
  46. int main() {
  47. 	int n, m;
  48. 	cin >> n >> m;
  49. 	for (int i = 0; i < m; i++){
  50. 		int a,b;
  51. 		cin >> a >> b;
  52. 		a--;
  53. 		b--;
  54. 		g[a][b] = 1;
  55. 		g[b][a] = 1;
  56. 	}
  57. 	mincut (n);
  58. 	cout << best_cost;
  59. 		return 0;
  60. }
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
2 1
1 2
stdout
copy 
1
https://ideone.com/74zFIc
Защита от копирования
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!