查错 CH Round #57

题目：http://ch.ezoj.tk/contest/CH%20Round%20%2357%20-%20Story%20of%20the%20OI%20Class/查错

题解：刚开始看见立马以为是 p1790拓扑编号，于是改了下输出就交了。。。

然后就爆零了。。。

仔细看题发现：

本题要求尽早处理编号小的点

尽量使编号小的点最早被处理

难道不一样？

后来发现了 p1790的样例：

5 4

4 1

1 3

5 3

2 5

然后就明白了

对p1790来说，要想1号尽早被处理，第一次就得处理4

而本题要求处理顺序最小那么第一次处理的必须得是2

然后就呵呵了

所以这两题的解法分别是：

本题：正向贪心，每次选取入度为0的且编号最小的点

p1790：反向贪心，反向建图，每次选取出度为0且编号最大的点

代码：（本题）

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<iostream>
 7 #include<vector>
 8 #include<map>
 9 #include<set>
10 #include<queue>
11 #include<string>
12 #define inf 1000000000
13 #define maxn 250000
14 #define maxm 500+100
15 #define eps 1e-10
16 #define ll long long
17 #define pa pair<int,int>
18 #define for0(i,n) for(int i=0;i<=(n);i++)
19 #define for1(i,n) for(int i=1;i<=(n);i++)
20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
22 #define mod 1000000007
23 using namespace std;
24 inline int read()
25 {
26     int x=0,f=1;char ch=getchar();
27     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
28     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
29     return x*f;
30 }
31 int n,m,head[maxn],inp[maxn],ans[maxn],cnt;
32 struct edge{int go,next;}e[maxn];
33 priority_queue<int,vector<int>,greater<int> >q;
34 int main()
35 {
36     freopen("input.txt","r",stdin);
37     freopen("output.txt","w",stdout);
38     n=read();m=read();
39     for1(i,m)
40     {
41         int x=read(),y=read();
42         e[i].go=y;e[i].next=head[x];head[x]=i;inp[y]++;
43     }
44     for1(i,n)if(!inp[i])q.push(i);
45     while(!q.empty())
46     {
47         int x=q.top();q.pop();ans[++cnt]=x;
48         for(int i=head[x],y;i;i=e[i].next)
49          {
50              inp[y=e[i].go]--;
51              if(!inp[y])q.push(y);
52          }
53     }
54     if(cnt<n)printf("OMG.
");else for1(i,n)printf("%d ",ans[i]);
55     return 0;
56 }

View Code

（p1790）

 1 var head,q,next,go,a,f,outp:array[0..201000] of longint;
 2     i,h,t,n,m,x,y,l,tot:longint;
 3 function get:longint;
 4  var i,k:longint;
 5  begin
 6  get:=a[1];
 7  a[0]:=a[l];dec(l);
 8  i:=1;k:=2;
 9  while k<=l do
10   begin
11   if (k<l) and (a[k]<a[k+1]) then inc(k);
12   if (a[0]<a[k]) then begin a[i]:=a[k];i:=k;k:=k<<1;end
13   else k:=l+1;
14   end;
15  a[i]:=a[0];
16  end;
17 procedure put(x:longint);
18  var i,k:longint;
19  begin
20  inc(l);
21  a[0]:=x;
22  i:=l;k:=l>>1;
23  while k>=1 do
24   begin
25   if a[0]>a[k] then begin a[i]:=a[k];i:=k;k:=k>>1;end
26   else k:=0;
27   end;
28  a[i]:=x;
29  end;
30 procedure init;
31  begin
32  readln(n,m);
33  for i:=1 to m do
34   begin
35   readln(x,y);
36   go[i]:=x;
37   next[i]:=head[y];
38   head[y]:=i;
39   inc(outp[x]);
40   end;
41  end;
42 procedure main;
43  begin
44  h:=0;t:=0;
45  for i:=1 to n do
46   if outp[i]=0 then
47    put(i);
48  tot:=n;
49  while l<>0 do
50   begin
51   x:=get;
52   f[x]:=tot;dec(tot);
53   i:=head[x];
54   while i<>0 do
55    begin
56    y:=go[i];
57    dec(outp[y]);
58    if outp[y]=0 then put(y);
59    i:=next[i];
60    end;
61   end;
62  for i:=1 to n do write(f[i],' ');
63  end;
64 begin
65  init;
66  main;
67 end.

View Code