首页 > 代码库 > usaco-1.3-wormhole
usaco-1.3-wormhole
这个属于DFS枚举：
/*ID: qq104801LANG: C++TASK: wormholeQQ:104804687*/#include <iostream>#include <fstream>#include <cstring>#include <vector>#include <queue>#include <stack>#include <algorithm>#include <cmath>using namespace std;#define loop(i,n) for(int i=0;i<(n);i++)#define loop2(i,n) for(int i=1;i<=(n);i++)const int maxn=13;const int inf=1<<30;int n,x[maxn],y[maxn];int partner[maxn],next_on_right[maxn];bool cycle_exists(void){ /* for(int i=1;i<=n;i++) cout<<i<<":"<<partner[i]<<" "; cout<<endl; */ for(int start=1;start<=n;start++) { int pos=start; for(int count=0;count<n;count++) pos=next_on_right[partner[pos]]; if(pos!=0) return true; } return false;}int solve(void){ int i,total=0; for(i=1;i<=n;i++) if(partner[i]==0)break; if(i>n) { if(cycle_exists()) return 1; else return 0; } for(int j=i+1;j<=n;j++) if(partner[j]==0) { partner[i]=j; partner[j]=i; total+=solve(); partner[i]=partner[j]=0; } return total;}void test(){ freopen("wormhole.in","r",stdin); freopen("wormhole.out","w",stdout); cin>>n; loop2(i,n) { cin>>x[i]>>y[i]; //cout<<x[i]<<":"<<y[i]<<endl; } loop2(i,n) loop2(j,n) if(x[j]>x[i]&&y[i]==y[j]) if(next_on_right[i]==0 || x[j]-x[i]<x[next_on_right[i]]-x[i]) next_on_right[i]=j; cout<<solve()<<endl;}int main () { test(); return 0;}
test data:
USACO TrainingGrader Results 4 users onlineCHN/2 IND/1 KAZ/1USER: cn tom [qq104801]TASK: wormholeLANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.008 secs, 3380 KB] Test 2: TEST OK [0.008 secs, 3380 KB] Test 3: TEST OK [0.005 secs, 3380 KB] Test 4: TEST OK [0.011 secs, 3380 KB] Test 5: TEST OK [0.008 secs, 3380 KB] Test 6: TEST OK [0.011 secs, 3380 KB] Test 7: TEST OK [0.011 secs, 3380 KB] Test 8: TEST OK [0.014 secs, 3380 KB] Test 9: TEST OK [0.016 secs, 3380 KB] Test 10: TEST OK [0.019 secs, 3380 KB]All tests OK.Your program (‘wormhole‘) produced all correct answers! This is your submission #2 for this problem. Congratulations!Here are the test data inputs:------- test 1 [length 18 bytes] ----40 01 01 10 1------- test 2 [length 23 bytes] ----421 711 2311 75 10------- test 3 [length 37 bytes] ----61 1520 1517 1122 2125 1120 17------- test 4 [length 117 bytes] ----6879221060 76350727161945371 76350727380619073 76350727896289713 76350727852891025 852349940519959866 76350727------- test 5 [length 159 bytes] ----8491007315 32453967799582962 578796531491007315 768974420373902710 57879653199582962 332416760946724340 321414549976998120 63822667649126574 437845706------- test 6 [length 198 bytes] ----10987878530 332490544545074228 332490544571194544 27896394332922985 229703843571194544 85133360390862786 28227282219975775 267376202219975775 33249054490862786 62367085872930617 951881113------- test 7 [length 243 bytes] ----12636437309 704270751695056713 700147825636437309 356396548921201220 589666013430411607 671693685324259336 671693685723442153 589666013528904109 419799944921201220 356396548723442153 856537355691516566 726853849941903572 634527403------- test 8 [length 53 bytes] ----120 01 02 03 04 05 06 07 08 09 010 110 0------- test 9 [length 243 bytes] ----12572085931 667578536964406504 667578536656852339 870264627110654368 823223484513786208 528178006620147001 528178006227047539 667578536656852339 528178006945298921 528178006945298921 870264627840030425 870264627828839382 528178006------- test 10 [length 236 bytes] ----125138254 91583927607865472 16750787651248250 8250417675467597 611809280157130071 946061365138261433 967068106769112165 966993974675467597 144175980769112165 47510559451248250 144175980947874168 111530133164921238 967068106
usaco-1.3-wormhole
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。