fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. const int N=105*2;
  8.  
  9. struct Search_t{
  10. 	int n;
  11. 	int G[N][N];
  12. 	int w[N][N];
  13. 	int op[N];
  14. 	int v[N];
  15. 	int used[N];
  16. 	int tmp_u[N];
  17. 	int ans,now;
  18.  
  19. 	bool Can_choose(int k){
  20. 		for (int i=1;i<=n;i++){
  21. 			if (v[i] && !used[i] && G[k][i]) return false;
  22. 			if (v[i] && used[i] && G[i][op[k]]) return false;
  23. 		}
  24. 		return true;
  25. 	}
  26.  
  27. 	int greedy(int k){
  28. 		int ret=0;
  29. 		for (int i=1;i<=n;i++) tmp_u[i]=used[i];
  30.         for (int i=k;i<=n;i++)
  31.             if (!v[i]){
  32.                 bool check=true;
  33.                 for (int j=1;j<=n;j++)
  34.                     if (v[j] && !used[j] && G[i][j]) { check=false; break; }
  35.                 if (!check) continue;
  36.                 ret+=w[i][i];
  37.                 for (int j=1;j<=n;j++)
  38.                     if (tmp_u[j])
  39.                         ret+=w[i][j];
  40.                 tmp_u[i]=1;
  41.             }
  42. 		return ret;
  43. 	}
  44.  
  45. 	void Choose(int k){
  46. 		v[k]=1;
  47. 		v[op[k]]=1;
  48. 		used[k]=1;
  49. 		now+=w[k][k];
  50. 		for (int i=1;i<=n;i++)
  51. 			if (v[i] && used[i] && i!=k) now+=w[i][k];
  52. 	}
  53.  
  54. 	void Remove(int k){
  55. 		v[k]=0;
  56. 		v[op[k]]=0;
  57. 		used[k]=0;
  58. 		now-=w[k][k];
  59. 		for (int i=1;i<=n;i++)
  60. 			if (v[i] && used[i] && i!=k) now-=w[i][k];
  61. 	}
  62.  
  63. 	void dfs(int dep){
  64. 		if (dep>n){
  65. 			if (now>ans) ans=now;
  66. 			return;
  67. 		}
  68. 		if (now+greedy(dep)<=ans)
  69.             return;
  70. 		if (v[dep]) dfs(dep+1);
  71. 		else{
  72. 			bool s1=Can_choose(dep);
  73. 			bool s2=Can_choose(op[dep]);
  74. 			if (s1 && s2){
  75. 				Choose(dep);
  76. 				int w1=now+greedy(dep+1);
  77. 				Remove(dep);
  78.  
  79. 				Choose(op[dep]);
  80. 				int w2=now+greedy(dep+1);
  81. 				Remove(op[dep]);
  82.  
  83. 				if (w1>w2){
  84. 					Choose(dep);
  85. 					dfs(dep+1);
  86. 					Remove(dep);
  87.  
  88. 					Choose(op[dep]);
  89. 					dfs(dep+1);
  90. 					Remove(op[dep]);
  91. 				}
  92. 				else{
  93. 					Choose(op[dep]);
  94. 					dfs(dep+1);
  95. 					Remove(op[dep]);
  96.  
  97. 					Choose(dep);
  98. 					dfs(dep+1);
  99. 					Remove(dep);
  100. 				}
  101. 			}
  102. 			else
  103. 			if (s1){
  104. 				Choose(dep);
  105. 				dfs(dep+1);
  106. 				Remove(dep);
  107. 			}
  108. 			else
  109. 			if (s2){
  110. 				Choose(op[dep]);
  111. 				dfs(dep+1);
  112. 				Remove(op[dep]);
  113. 			}
  114. 		}
  115. 	}
  116.  
  117. 	void gao(){
  118. 		memset(v,0,sizeof(v));
  119. 		memset(used,0,sizeof(used));
  120. 		now=0;
  121. 		ans=0;
  122. 		dfs(1);
  123. 		printf("%d\n",ans);
  124. 	}
  125. }Search;
  126. #define op(x) ((x)>n?(x)-n:(x)+n)
  127. int m,n,Cn;
  128. int mat[N][N];
  129. int G[N][N];
  130. int Only[N][N];
  131. int Color[N];
  132. int P;
  133.  
  134. void solve(){
  135. 	memset(G,0,sizeof(G));
  136. 	for (int i=1;i<=2*n;i++)
  137. 		for (int j=1;j<=2*n;j++)
  138. 			if (mat[i][j] && Color[i]!=Color[j])
  139. 				G[Color[i]][Color[j]]=1;
  140. 	memset(Only,0,sizeof(Only));
  141. 	for (int i=1;i<=n;i++){
  142. 		Only[Color[i]][Color[op(i)]]=1;
  143. 		Only[Color[op(i)]][Color[i]]=1;
  144. 	}
  145. 	memcpy(Search.G,G,sizeof(G));
  146. 	memset(Search.w,0,sizeof(Search.w));
  147. 	for (int i=1;i<=Cn;i++)
  148. 		for (int j=1;j<=Cn;j++)
  149. 			if (Only[i][j]){
  150. 				Search.op[i]=j;
  151. 				Search.op[j]=i;
  152. 			}
  153. 	Search.n=Cn;
  154. 	for (int i=0;i<P;i++){
  155. 		int a,b,x,y,w;
  156. 		scanf("%d%d%d%d%d",&a,&x,&b,&y,&w);
  157. 		if (x==0) a+=n;
  158. 		if (y==0) b+=n;
  159. 		Search.w[Color[a]][Color[b]]+=w;
  160. 		if (Color[a]!=Color[b]) Search.w[Color[b]][Color[a]]+=w;
  161. 	}
  162. 	Search.gao();
  163. }
  164.  
  165. int main(){
  166. 	while (scanf("%d%d%d",&n,&m,&P)!=EOF){
  167. 		memset(mat,0,sizeof(mat));
  168. 		for (int i=0;i<m;i++){
  169. 			int x,y,c;
  170. 			char oper[10];
  171. 			char Tmp[10];
  172. 			scanf("%d %s %d %s %d",&x,oper,&y,Tmp,&c);
  173. 			switch (oper[0]){
  174. 				case 'x':
  175. 					if (c){
  176. 						mat[x][op(y)]=1;
  177. 						mat[y][op(x)]=1;
  178. 						mat[op(x)][y]=1;
  179. 						mat[op(y)][x]=1;
  180. 					}
  181. 					else{
  182. 						mat[x][y]=1;
  183. 						mat[y][x]=1;
  184. 						mat[op(x)][op(y)]=1;
  185. 						mat[op(y)][op(x)]=1;
  186. 					}
  187. 					break;
  188. 				case 'o':
  189. 					if (c){
  190. 						mat[op(x)][y]=1;
  191. 						mat[op(y)][x]=1;
  192. 					}
  193. 					else{
  194. 						mat[x][op(x)]=1;
  195. 						mat[y][op(y)]=1;
  196. 					}
  197. 					break;
  198. 				case 'a':
  199. 					if (c){
  200. 						mat[op(x)][x]=1;
  201. 						mat[op(y)][y]=1;
  202. 					}
  203. 					else{
  204. 						mat[x][op(y)]=1;
  205. 						mat[y][op(x)]=1;
  206. 					}
  207. 					break;
  208. 			}
  209. 		}
  210. 		for (int k=1;k<=2*n;k++)
  211. 			for (int i=1;i<=2*n;i++)
  212. 				for (int j=1;j<=2*n;j++)
  213. 					mat[i][j]|=mat[i][k]&mat[k][j];
  214. 		Cn=0;
  215. 		memset(Color,0,sizeof(Color));
  216. 		for (int i=1;i<=2*n;i++)
  217. 			if (!Color[i]){
  218. 				Color[i]=++Cn;
  219. 				for (int j=1;j<=2*n;j++)
  220. 					if (mat[i][j] && mat[j][i])
  221. 						Color[j]=Cn;
  222. 			}
  223. 		bool check=true;
  224. 		for (int i=1;i<=n;i++)
  225. 			if (Color[i]==Color[op(i)]) check=false;
  226. 		if (!check) puts("No solution");
  227. 			   else solve();
  228. 	}
  229. 	return 0;
  230. }
  231.  
Success #stdin #stdout 0.01s 3592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UnUkI
language:
C++ (gcc 8.3)
created:
12 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!