首页 > 代码库 > noip模拟题《戏》game
noip模拟题《戏》game
【问题背景】
zhx 和他的妹子（们） 做游戏。
【问题描述】
考虑 N 个人玩一个游戏，任意两个人之间进行一场游戏（共 N*(N-1)/2 场），且每场一定能分出胜负。
现在， 你需要在其中找到三个人构成“剪刀石头步”局面： 三个人 A，B，C满足A战胜B，B 战胜 C，C 战胜 A。
【输入格式】
第一行一个正整数 N， 表示参加游戏的人数。
接下来 N 行， 每行 N 个数 0/1，中间没有空格隔开。第i行第j列数字为1表示 i 在游戏中战胜了 j。 所有对角线元素（即第 i 行第 i 个元素） 为 0，保证数据合法。
【输出格式】
如果存在三个人构成“剪刀石头布”局面， 输出三个人的编号（从 1 开始）。
如果不存在这样的三个人， 输出一个数-1。
【样例输入】
5
00100
10000
01001
11101
11000
【样例输出】
1 3 2
【数据规模与约定】
对于50%的数据，1 ≤n≤ 500。
对于80%的数据，1 ≤n≤ 1000。
对于100%的数据，1 ≤n≤ 5000。
啦啦啦第一次直接n3暴力了
正解：
由于这是一个竞赛图，每两个点之间有且仅有一条有向边，所以当我们找到一个任意长度的环时，考虑这个环上的前三个点A,B,C，若C与A之间的边由C指向A，则找到一个三元环，否则从A指向C有一条边，在这个环上删去B，加上C->A的边，就得到了一个点数少一个的环。
下面只需考虑如何找一个任意长度的环：对图进行dfs，以v数组存下每个点的遍历状态，0表示没有访问过，1表示访问过但从这个点延伸出的路径上的点还没有访问完，2表示已经访问过这个点及它延伸出的路径上所有的点。这样当我们在dfs中发现又扩展到一个状态为1的点，就找到了一个环。
1 program game(input,output); 2 var 3 a:array[0..5050,0..5050]of boolean; 4 f,v,s:array[0..5050]of longint; 5 c:char; 6 i,j,n,m,t:longint; 7 procedure work; 8 begin 9 for i:=1 to m>>1 do begin t:=f[i];f[i]:=f[m-i+1];f[m-i+1]:=t; end; 10 j:=1; 11 for i:=2 to m do if f[i]<f[j] then j:=i; 12 for i:=1 to m do begin t:=i+j-1;if t>m then t:=t-m;v[i]:=f[t]; end; 13 for i:=1 to m do f[i]:=v[i]; 14 //writeln(m); 15 //for i:=1 to m do writeln(f[i]); 16 for i:=3 to m do 17 if a[f[i],f[1]] then begin write(f[1],‘ ‘,f[i-1],‘ ‘,f[i]);close(input);close(output);halt; end; 18 end; 19 procedure dfs(k,d:longint); 20 var 21 i:longint; 22 begin 23 v[k]:=1; 24 s[d]:=k; 25 for i:=1 to n do if a[k,i] then 26 begin 27 if v[i]=2 then continue; 28 if v[i]=1 then 29 begin 30 m:=1;f[1]:=i;j:=d; 31 while s[j]<>i do begin inc(m);f[m]:=s[j];dec(j); end; 32 work; 33 end; 34 dfs(i,d+1); 35 end; 36 v[k]:=2; 37 end; 38 begin 39 assign(input,‘game.in‘);assign(output,‘game.out‘);reset(input);rewrite(output); 40 readln(n); 41 for i:=1 to n do begin for j:=1 to n do begin read(c);if c=‘1‘ then a[i,j]:=true else a[i,j]:=false; end;readln; end; 42 for i:=1 to n do if v[i]=0 then dfs(i,1); 43 write(-1); 44 close(input);close(output); 45 end.
noip模拟题《戏》game