首页 > 代码库 > 复杂的按钮
复杂的按钮
复杂的按钮
(button.pas/c/cpp)
【题目描述】
小K在遗迹探险时遇到了N个按钮，刚开始所有的按钮都处于开状态，小K的经验告诉他把所有的按钮都关上会有“好事”发生，可是有些按钮按下时会让其他一些已经闭合的按钮弹开。经过研究，每个按钮都对应着一个固定的弹开集合，这个按钮按下时，弹开集合中所有的按钮都会变为开状态。现在小K想知道是否能让所有的按钮变为闭合状态。如果能，打印最少步数以及方案，否则，打印“no solution”。
【输入格式】
第一行一个整数N，表示按钮的个数；
接下来N行，表示编号为1到N个按钮的弹开集合，格式为Mi，B1B2B3...BMi，表示编号为i的按钮按下时，会让编号为B1B2B3...BMi的按钮弹开(注：其中不会出现重复)
【输出格式】
如果无解，输出“no solution”;否则，第一行输出最少步数ret，第二行输出ret个数，表示按顺序按下编号为这些数的按钮就可以解决，每2个整数之间用一个空格隔开；如果有多种方案，请输出字典序最小的方案。
【样例输入】
6
2 2 3
0
2 4 5
0
0
0
【样例输出】
6
1 2 3 4 5 6
【数据规模】
对于40%的数据： 1≤N≤10；
对于100%的数据：1≤N≤30,000；令M=M1+M2+M3+...+MN，则0≤M≤1,000,000；
首先，要看出来这是个鬼畜的图论题。咋么看出来的？比方说，按钮1，不受任何按钮的牵制，更何况他的序号更小，那么肯定先按他，以后就不会再次按到他了。那么我们说第一问的答案如果有解肯定是n。为什么？举个例子，所有按钮都没牵制任何按钮，那么最少最少，也需要按n次。因为你需要的是按下每一个按钮，而每个按钮原来都是开着的，而且只能是自己按下按钮，而不是按下其他按钮导致的，所以得出ans1>=n。那么如果ans1>n，就说明n次以后肯定剩下了几个按钮，比如1,5,6。那么如果再按下1,5,6，必定又会有按钮弹起，比如2,5。那么如此反复，是永远得不到结果的，说明有解的情况ans1=n。那么再回到图论，解决第二问。如果某一个按钮不受别人牵制，那么就相当于他的入度为0嘛。那么，相应的，如果a牵制b，那么a到b就有一条有向边。那么，首先我们要按下的肯定都是入度为0的结点，然后把相应的边删了。当然，如果没有结点入度为0，那就是有环了，肯定无解了。那么，我们每次要找个入度为0且序号最小的结点，把他输出，并且修改相应边与相应的点，如此反复。那么这样的效率是n^2的，100分别想。那么，我们每次取个序号最小的，这里用了o(n)的时间，所以这里可以优下来，就是调队。每次用logn时间get，在删边的同时，判断他的子节点入度是否为0，为0则入堆。最后什么时候结束？len=0，即堆为空的时候，那么这题就解完了。
1 var n,i,j,p,x,min,tot,t,len:longint; 2 out_,in_,a,heap:array[0..30005] of longint; 3 son,nxt:array[0..1000005] of longint; 4 lnk:array[0..30005] of longint; 5 procedure print_no; 6 begin 7 writeln(‘no solution‘); 8 close(input); close(output); 9 halt; 10 end; 11 procedure put(id:longint); 12 var i:longint; 13 begin 14 inc(len); heap[len]:=id; i:=len; 15 while (i>1) do 16 begin 17 if (heap[i>>1]>heap[i]) then 18 begin 19 heap[0]:=heap[i]; heap[i]:=heap[i>>1]; heap[i>>1]:=heap[0]; 20 i:=i>>1; 21 end 22 else break; 23 end; 24 end; 25 function get:longint; 26 var fa,son:longint; 27 begin 28 get:=heap[1]; heap[1]:=heap[len]; dec(len); fa:=1; 29 while (fa<<1<=len) do 30 begin 31 if (fa<<1+1>len) or (heap[fa<<1]<heap[fa<<1+1]) then son:=fa*2 32 else son:=fa*2+1; 33 if heap[fa]>heap[son] then 34 begin 35 heap[0]:=heap[fa]; heap[fa]:=heap[son]; heap[son]:=heap[0]; 36 fa:=son; 37 end 38 else break; 39 end; 40 end; 41 procedure add(x,y:longint); 42 begin 43 inc(tot); son[tot]:=y; nxt[tot]:=lnk[x]; lnk[x]:=tot; 44 end; 45 begin 46 readln(n); 47 for i:=1 to n do 48 begin 49 read(out_[i]); 50 for j:=1 to out_[i] do 51 begin 52 read(x); inc(in_[x]); add(i,x); 53 end; 54 end; 55 min:=maxlongint; 56 for i:=1 to n do 57 if (in_[i]=0) then begin min:=0; put(i); end; 58 if min<>0 then print_no; 59 repeat 60 p:=get; inc(t); a[t]:=p; j:=lnk[p]; 61 in_[p]:=-1; 62 while j<>0 do 63 begin 64 dec(in_[son[j]]); 65 if in_[son[j]]=0 then put(son[j]); 66 j:=nxt[j]; 67 end; 68 until len=0; 69 writeln(t); 70 for i:=1 to t do write(a[i],‘ ‘); 71 end.
复杂的按钮