fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include<set>
  6. #include <cmath>
  7. #include<sstream>
  8. #include<queue>
  9. #include<vector>
  10. #include<stdio.h>
  11. #include<stack>
  12. #include<deque>
  13. #include<bitset>
  14. #include<string>
  15. #include<cstdio>
  16. #include<map>
  17. #include<iterator>
  18. #include<iomanip>
  19. #define prfs(x) printf("%s\n",x.c_str())
  20. #define prfi(x) printf("%d\n",x);
  21. #define sfi(X) scanf("%d",&X);
  22. #define lop(i,n) for (int i = 0 ; i < n ;i++)
  23. #define blop(i,n) for(int i = n-1 ; i>=0;i--)
  24. #define M_P make_pair
  25. #define All(X) (X).begin(),(X).end()
  26. #define SZ(n) (int)(n).size()
  27. #define voi vector<int>
  28. #define vos vector<string>
  29. #define vob vector<bool>
  30. #define vovi vector<vector<int > >
  31. #define vob vector<bool>
  32. #define ll long long 
  33. using namespace std;
  34. map<string, int> person, club, party;
  35. int matrix[1300][1300];
  36. int n = 2;
  37. int p[1300];
  38. int f = 0;
  39. int ID(string one,int a) {
  40. 	if (a == 1) {
  41. 		if (!person[one])return person[one] = ++n;
  42. 		return person[one];
  43. 	}
  44. 	else if (a == 2) {
  45. 		if (!club[one])return club[one] = ++n;
  46. 		return club[one];
  47. 	}
  48. 	if (!party[one])return party[one] = ++n;
  49. 	return party[one];
  50. }
  51. void updatePath(int t, int minEdge) {
  52. 	if (t == 1) {
  53. 		f = minEdge;
  54. 		return;
  55. 	}
  56. 	else if (p[t] != -1) {
  57. 		updatePath(p[t], min(minEdge, matrix[p[t]][t]));
  58. 		matrix[p[t]][t] -= f;
  59. 		matrix[t][p[t]] += f;
  60. 	}
  61. }
  62.  
  63. int Ed(int s,int t) {
  64. 	int mf = 0;
  65. 	while (1) {
  66. 		memset(p, -1, sizeof p);
  67. 		f = 0;
  68. 		queue<int> q;
  69. 		q.push(1);
  70. 		while (!q.empty()) {
  71. 			int u = q.front();q.pop();
  72. 			if (u == t)break;
  73. 			for (int i = 1;i <= n;i++) {
  74. 				if (p[i] == -1 && matrix[u][i] > 0) {
  75. 					p[i] = u, q.push(i);
  76. 				}
  77. 			}
  78.  
  79. 		}
  80. 		updatePath(t, (int)1e9);
  81. 		if (!f)break;
  82. 		mf += f;
  83.  
  84. 	}
  85. 	return mf;
  86. }
  87. int main(){
  88. 	freopen("src.txt", "r", stdin);
  89. 	int T;
  90. 	scanf("%d\n", &T);
  91. 	string z;
  92. 	while (T--) {
  93. 		n = 2;
  94. 		memset(matrix, 0, sizeof matrix);
  95. 		party.clear(), club.clear(), person.clear();
  96. 		while (getline(cin, z) && z.length() > 0) {
  97. 			istringstream mycin(z);
  98. 			string a, b;
  99. 			mycin >> a >> b;
  100. 			int ia = ID(a, 1), ip = ID(b, 3), ic;
  101. 			 matrix[ip][ia] = 1;
  102. 			while (mycin >> b) {
  103. 			ic = ID(b,2);
  104. 				matrix[ia][ic] = 1;
  105. 				matrix[ic][2] = 1;
  106. 			}
  107. 		}
  108. 		int cl = club.size();
  109. 		for (map<string,int>::iterator  i = party.begin(); i!=party.end(); i++) {
  110. 			matrix[1][i->second] = (cl-1) / 2;
  111. 		}
  112. 		int total = Ed(1,2);
  113. 		if (total == cl) {
  114. 			for (map<string, int>::iterator it1 = person.begin(); it1 != person.end();it1++) {
  115. 				for (map<string, int>::iterator it2 = club.begin(); it2 != club.end();it2++) {
  116. 					if (matrix[it2->second][it1->second]) {
  117. 						printf("%s %s\n", it1->first.c_str(), it2->first.c_str());
  118. 					}
  119. 				}
  120. 			}
  121. 		}
  122. 		else {
  123. 			printf("Impossible.\n");
  124. 		}
  125. 		if (T)printf("\n");
  126. 	}
  127.  
  128.  
  129. 	return 0;
  130. }
Success #stdin #stdout 0s 10024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Sk1fKN
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!