Milking Order

题意:给出m个描述状态，其中包含若干个边的关系，问最多能取x (x<=m)个状态，使得形成的图没有环。就是说取x个状态，用状态中的关系建边，其中不能有环。

题解：最大化x？和二分答案有点关系。所以首先要二分x，判断是否有环。这个可以用拓扑或者tarjan。我用的是拓扑，判环的依据是队尾t是否等于n，如果不等于n，则一定有环。(只有入度等于1才进队)于是操作就有点复杂了，（我会在程序里标记）。最后因为要字典序最小，要用堆来输出答案。

  1 var
  2 q,head,next,rd,a,b,id,ans,f:array[0..500005]of longint;
  3 e,i,j,mid,x,y,z,l,r,t,len,n,k,tot,m:longint;
  4 procedure add(x,y:longint);
  5  begin
  6   inc(e);next[e]:=head[x];head[x]:=e; a[e]:=y;id[e]:=i;
  7  end;
  8  function check(mid:longint):boolean;
  9 
 10   var i,h,tail:longint;
 11    begin
 12    fillchar(rd,sizeof(rd),0);
 13    fillchar(q,sizeof(q),0);
 14    tail:=0; t:=0;
 15     for i:=1 to e do
 16      begin
 17        if id[i]<=mid then
 18          begin
 19            inc(rd[a[i]]);
 20          end;
 21      end;
 22   
 23  for i:=1 to n do
 24    if rd[i]=0 then
 25      begin
 26        inc(t);
 27        inc(tail);
 28        q[tail]:=i;
 29      end;
 30      if tail=0 then exit(false);
 31      h:=0;
 32      while h<tail do
 33       begin
 34          inc(h);
 35          i:=head[q[h]];
 36         while  (id[i]>mid)and(i>0) do begin i:=next[i];  end;// 判断边是否超过mid
 37 
 38            while (i>0) do
 39               begin
 40                dec(rd[a[i]]);
 41                if rd[a[i]]=0 then
 42                  begin
 43                    inc(t);inc(tail);q[tail]:=a[i];
 44                  // if mid =3 then  writeln(tail);
 45                  end;
 46                i:=next[i];
 47                while (i>0)and(id[i]>mid) do i:=next[i]; //同样判断
 48               end;
 49       end;
 50   
 51     if t=n then exit(true) else exit(false);
 52   end;
 53   procedure make(x:longint);
 54  var now,father,t:longint;
 55   begin
 56   inc(len);
 57   f[len]:=x;
 58   now:=len;
 59    while (now>1)and(f[now>>1]>f[now]) do
 60     begin
 61       father:=now>>1;
 62          t:=f[father];
 63          f[father]:=f[now];
 64          f[now]:=t;
 65          now:=father;
 66     end;
 67  end;
 68 
 69   function detele:longint;
 70   var fa,son,t:longint;
 71       ss:boolean;
 72    begin
 73    k:=f[1];
 74    f[1]:=f[len];
 75    dec(len);
 76    fa:=1;ss:=false;
 77     while ((fa*2<=len)or(fa*2+1<=len))and(not ss) do
 78      begin
 79          if (fa*2+1>len) or(f[fa*2]<f[fa*2+1]) then
 80          son:=fa*2  else son:=fa*2+1;
 81          if f[fa]>f[son] then
 82            begin
 83             t:=f[fa];
 84             f[fa]:=f[son];
 85             f[son]:=t;
 86           fa:=son;
 87       end
 88        else break;
 89   end;
 90  end;
 91 
 92 begin
 93 readln(n,m);
 94 for i:=1 to m do
 95  begin
 96    read(x);
 97    for j:=1 to x do
 98     begin
 99       read(y);
100       if j>1 then begin  add(z,y); end;
101       z:=y;
102     end;
103  end;
104 l:=0;r:=m;
105 while l<=r do//二分答案模板（
106  begin
107    mid:=(l+r) div 2;
108    //writeln(l,' ',r);
109    if check(mid) then l:=mid+1 else r:=mid-1;
110   
111  end;
112  l:=l-1;//直到这里）
113 
114    fillchar(rd,sizeof(rd),0);
115    for i:=1 to e do
116      begin
117        if id[i]<=l then
118          begin
119            inc(rd[a[i]]);
120          end;
121      end;
122     for i:=1 to n do
123       begin
124         if rd[i]=0 then make(i);//堆操作
125       end;
126      tot:=0;
127     while tot<n  do
128    begin
129      inc(tot);
130      detele;
131      write(k,' ');//堆操作
132       i:=head[k];
133       while (id[i]>l)and(i>0) do i:=next[i];//判断是否大于二分答案的最终答案
134 
135       while i>0 do
136         begin
137          dec(rd[a[i]]);
138          if rd[a[i]]=0 then make(a[i]);
139          i:=next[i];
140          while (i>0)and(id[i]>mid) do i:=next[i];//也需要判断
141         end;
142    end;
143 end.

NOIP2018 rp++