首页 > 代码库 > usa-4.3-race3-passed
usa-4.3-race3-passed
这个题目，分割，还没有找到更好的方法。但也过了：
/*ID: qq104801LANG: C++TASK: race3*/#include <iostream>#include <fstream>#include <cstring>#include <vector>#include <queue>#include <stack>#include <algorithm>using namespace std;const int inf=1<<30;const int nmax=52;int a[nmax][nmax];bool v[nmax];int ans[nmax],ans1[nmax];int u=-1,temp=0;void debug_dummpy(){ return;}bool bfs(void){ int d[100]={0},head=1,tail=1; bool h[51]={1,0}; while(head<=tail){ int now=d[head++]; for(int i=1;i<=a[now][0];i++) { int& t=a[now][i]; if(!h[t]&&!v[t]) h[d[++tail]=t]=true; } } return !h[temp];}bool bfs2(void){ int d[100]={0},tail=1,head=1; int level[100]={0}; level[0]=1;int k=0; while(head<=tail){ int now=d[head++]; if(v[now]){k=now;continue;} for(int i=1;i<=a[now][0];i++) { int& t=a[now][i]; if(!level[t]) level[d[++tail]=t]=1; } } level[k]=2; memset(d,0,sizeof d);head=1;tail=1;d[1]=k; while(head<=tail){ int now=d[head++]; for(int i=1;i<=a[now][0];i++) { int& t=a[now][i]; if(level[t]==1)return false; if(!level[t]) level[d[++tail]=t]=2; } } return true;}void test(){ freopen("race3.in","r",stdin); freopen("race3.out","w",stdout); cin>>u; while(u!=-1) { while(u!=-2) { a[temp][++a[temp][0]]=u; cin>>u; } cin>>u; temp++; } temp--; for(int i=1;i<temp;i++) { v[i]=true; if(bfs())ans[++ans[0]]=i; if(bfs2())ans1[++ans1[0]]=i; v[i]=false; } for(int i=0;i<ans[0];i++)cout<<ans[i]<<" "; cout<<ans[ans[0]]<<endl; for(int i=0;i<ans1[0];i++)cout<<ans1[i]<<" "; cout<<ans1[ans1[0]]<<endl;}int main () { test(); return 0;}
test data:
USACO TrainingGrader Results 8 users onlineCHN/3 EGY/1 IND/1 IRN/1 NED/1 USA/1USER: cn tom [qq104801]TASK: race3LANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.005 secs, 3384 KB] Test 2: TEST OK [0.003 secs, 3384 KB] Test 3: TEST OK [0.003 secs, 3384 KB] Test 4: TEST OK [0.003 secs, 3384 KB] Test 5: TEST OK [0.003 secs, 3384 KB] Test 6: TEST OK [0.003 secs, 3384 KB] Test 7: TEST OK [0.003 secs, 3384 KB] Test 8: TEST OK [0.003 secs, 3384 KB] Test 9: TEST OK [0.003 secs, 3384 KB] Test 10: TEST OK [0.003 secs, 3384 KB] Test 11: TEST OK [0.003 secs, 3384 KB]All tests OK.YOUR PROGRAM (‘race3‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated congratulations.Here are the test data inputs:------- test 1 ----1 -2-2-1------- test 2 ----1 2 -23 -23 -25 4 -26 4 -26 -27 8 -29 -25 9 -2-2-1------- test 3 ----1 2 -23 -23 -24 5 -26 -26 -27 8 -29 -29 5 -2-2-1------- test 4 ----1 -24 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 -23 -248 49 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 3 -2-2-1------- test 5 ----1 -22 -23 -24 -25 -26 -27 -28 -29 -210 -211 -212 -213 -214 -215 -216 -217 -218 -219 -220 -221 -222 -223 -224 -225 -226 -227 -228 -229 -230 -231 -232 -233 -234 -235 -236 -237 -238 -239 -240 -241 -242 -243 -244 -245 -246 -247 4 -248 -249 -2-2-1------- test 6 ----1 -22 1 -23 0 -23 4 -25 0 -27 6 -27 -28 -2-2-1------- test 7 ----1 -24 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 -23 48 -249 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 -22 3 -2-2-1------- test 8 ----1 -22 -23 -24 -25 -26 -27 -28 -29 -210 -211 -212 -213 -214 -215 -216 -217 -218 -219 -220 -221 -222 -223 -224 -225 -226 -227 -228 -229 -230 -231 -232 -233 -234 -235 -236 -237 -238 -239 -240 -241 -242 -243 -244 -245 -246 -247 -248 -249 -2-2-1------- test 9 ----1 -22 1 -23 0 -23 4 -25 0 -25 7 6 -27 -28 -2-2-1------- test 10 ----1 2 -22 3 -23 4 -24 5 -25 6 -26 7 -27 8 -28 9 -29 10 -210 11 -211 12 -212 13 -213 14 -214 15 -215 16 -216 17 -217 18 -218 19 -219 20 -220 21 -221 22 -222 23 -223 24 -224 25 -225 26 -226 27 -227 28 -228 29 -229 30 -230 31 -231 32 -232 33 -233 34 -234 35 -235 36 -236 37 -237 38 -238 39 -239 40 -240 41 -241 42 -242 43 -243 44 -244 45 -245 46 -246 47 -247 48 -248 49 -249 -2-2-1------- test 11 ----1 -22 0 -23 1 -24 2 -25 3 -26 4 -27 5 -28 6 -29 7 -210 8 -211 9 -212 10 -213 11 -214 12 -215 13 -216 14 -217 15 -218 16 -219 17 -220 18 -221 19 -222 20 -223 21 -224 22 -225 23 -226 24 -227 25 -228 26 -229 27 -230 28 -231 29 -232 30 -233 31 -234 32 -235 33 -236 34 -237 35 -238 36 -239 37 -240 38 -241 39 -242 40 -243 41 -244 42 -245 43 -246 44 -247 45 -248 46 -249 47 -2-2-1Keep up the good work!Thanks for your submission!
usa-4.3-race3-passed
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。