fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <vector>
  5. #include <climits>
  6. #include <algorithm>
  7. using namespace std;
  8. #define lli long long int
  9. #define INF 1000000
  10. #define ND 200
  11. #define ED 10000
  12. int n,m,eg_no,st,en;
  13. int to[ED],last[ND],nx[ED],hlf[ND],ds[ND],Q[ND],cap[ED],cap1[ED];
  14. void init()
  15. {
  16.     eg_no=0;
  17.     memset(last,-1,sizeof(last));
  18. }
  19. void add_edge(int u,int v,int cp,int r_cp)
  20. {
  21.     to[eg_no]=v;cap1[eg_no]=cp;cap[eg_no]=cp;nx[eg_no]=last[u];last[u]=eg_no++;
  22.     to[eg_no]=u;cap1[eg_no]=r_cp;cap[eg_no]=r_cp;nx[eg_no]=last[v];last[v]=eg_no++;
  23. }
  24. bool bfs()
  25. {
  26.     memset(ds,-1,sizeof(ds));
  27.     ds[st]=0;int p=1,q=0;Q[0]=st;
  28.     while(q<p)
  29.     {
  30.         int u=Q[q];
  31.         for(int i=last[u];i>=0;i=nx[i])
  32.         {
  33.             int v=to[i];
  34.             if(cap[i]>0 && ds[v]==-1)
  35.             {
  36.                 ds[v]=ds[u]+1;
  37.                 Q[p++]=v;
  38.             }
  39.         }
  40.         q++;
  41.     }
  42.     return (ds[en]!=-1);
  43. }
  44. int dfs(int in,int cp)
  45. {
  46.     if(in==en) return cp;
  47.     for(int &i=hlf[in];i>=0;i=nx[i])
  48.     {
  49.         if(cap[i]>0 && ds[in]+1==ds[to[i]])
  50.         {
  51.             int tmp=dfs(to[i],min(cp,cap[i]));
  52.             if(tmp>0)
  53.             {
  54.                 cap[i]-=tmp;
  55.                 cap[i^1]+=tmp;
  56.                 return tmp;
  57.             }
  58.         }
  59.     }
  60.     return 0;
  61. }
  62. int dinitz()
  63. {
  64.     int res=0;
  65.     while(bfs())
  66.     {
  67.         for(int i=0;i<=en;i++) hlf[i]=last[i];
  68.         while(1)
  69.         {
  70.             int ans=dfs(st,INF);
  71.             res+=ans;
  72.             if(ans<=0) break;
  73.         }
  74.     }
  75.     return res;
  76. }
  77. void func()
  78. {
  79. 	//freopen("test.txt","r",stdin);
  80. 	//freopen("testo.txt","w",stdout);
  81.  
  82. 	int no=0;
  83.  
  84. 	int n;
  85. 	cin>>n;
  86. 	int ct[10];
  87. 	for(int i=1;i<=9;i++) cin>>ct[i];
  88. 	vector<int>v[n+1];
  89. 	for(int i=1;i<=n;i++)
  90. 	{
  91. 		int k,ele;
  92. 		cin>>k;
  93. 		for(int j=1;j<=k;j++)
  94. 		{
  95. 			cin>>ele;
  96. 			v[i].push_back(ele);
  97. 		}
  98. 	}
  99.  
  100. 	vector<int>an;
  101. 	int se=1,fl;
  102. 	st=n+9+1,en=n+9+2;
  103. 	while(1)
  104. 	{
  105. 		if(se>n) break;
  106. 		fl=0;
  107. 		int ans=-1;
  108. 		for(int i=0;i<v[se].size();i++)
  109. 		{
  110. 			int p=v[se][i];
  111. 			ans=p;
  112. 			if(ct[p]<=0) continue;
  113.  
  114. 			ct[p]--;
  115.  
  116. 			init();
  117. 			for(int j=se+1;j<=n;j++) add_edge(st,j,1,0);
  118. 			for(int j=1;j<=9;j++)
  119. 				if(ct[j]>0)
  120. 					add_edge(n+j,en,ct[j],0);
  121. 			for(int j=se+1;j<=n;j++)
  122. 				for(int k=0;k<v[j].size();k++)
  123. 					add_edge(j,n+v[j][k],1,0);
  124.  
  125. 			int m=dinitz();
  126. 			if(m==(n-se))
  127. 			{
  128. 				fl=1;
  129. 				break;
  130. 			}
  131. 			ct[p]++;
  132. 		}
  133. 		if(fl==0)
  134. 		{
  135. 			no=1;
  136. 			break;
  137. 		}
  138. 		an.push_back(ans);
  139. 		se++;
  140. 	}
  141. 	if(no==0)
  142. 	{
  143. 		for(int i=0;i<an.size();i++) cout<<an[i]<<" ";
  144. 		cout<<"\n";
  145. 	}
  146. 	else cout<<"It seems MSG\n";
  147. }
  148. int main()
  149. {
  150. 	int t;
  151. 	t=1;
  152. 	while(t--)
  153. 	{
  154. 		func();
  155. 	}
  156. 	return 0;
  157. }
Runtime error #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1v89eI
language:
C++ (gcc 8.3)
created:
9 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!