POJ 1904

题目大意：有n个王子和n个美人，每个王子喜欢一些美人，如果一个王子要娶一个美人，必须是他喜欢的。现在国王的巫师给出了一个完美匹配表（每个王子都能娶到他喜欢的女孩），现在国外想知道在不影响全部王子能娶到老婆的前提下，每个王子能有哪些选择？

解：重复许多人的话：这是一条好题。一开始我自己觉得意识模糊，于是不断删去唯一的匹配边（只有一个王子喜欢的女孩和只喜欢一个女孩的王子），然后默认其他的都可以替换。其实也意识到了是一个增广路的模型，只是没有去细想，想当然会tle的。

正解则是在增广路的基础上，因为给出了一个完美匹配。所以设目前王子为xi，他初始匹配的美人为yi，如果王子选择了其他美人，则有一条增广路出去，但奇妙的事情发生了，如果这个增广路可行的话，则一定有一位王子会娶掉yi，如果连一条yi到xi的边，这条路径就成了一个环！！这路径包含的点成为了一个强连通分量，所以我们用连边建图，tarjan后处理顺序输出即可。

View Code

  1 const
  2         maxm=211111 << 1;
  3         maxn=2111;
  4 type
  5         data=record
  6           dest, next, op: longint;
  7         end;
  8 var
  9         edge: array[1..maxm]of data;
 10         ans, s, dfn, low, vect, col: array[1..maxn*2]of longint;
 11         visit: array[1..maxn*2]of boolean;
 12         time, stot, color, tot, n: longint;
 13 procedure add(x, y: longint);
 14 begin
 15   inc(tot);
 16   with edge[tot] do begin
 17     dest := y;
 18     next := vect[x];
 19     vect[x] := tot;
 20   end;
 21 end;
 22 
 23 procedure init;
 24 var
 25         i, j, x, y: longint;
 26 begin
 27   tot := 0;
 28   fillchar(vect, sizeof(vect), 0);
 29   readln(n);
 30   for i := 1 to n do begin
 31     read(x);
 32     for j := 1 to x do begin
 33       read(y);
 34       add(i, y+n);
 35     end;
 36     readln;
 37   end;
 38   for i := 1 to n do begin
 39     read(x);
 40     add(x+n, i);
 41   end;
 42   readln;
 43 end;
 44 
 45 procedure tarjan(x: longint);
 46 var
 47         i, u: longint;
 48 begin
 49   inc(time);
 50   dfn[x] := time; low[x] := time;
 51   inc(stot);
 52   s[stot] := x; visit[x] := true;
 53   i := vect[x];
 54   while i<>0 do
 55     with edge[i] do begin
 56       if dfn[dest]=0 then begin
 57         tarjan(dest);
 58         if low[dest]<low[x] then low[x] := low[dest];
 59       end
 60         else if visit[dest] then begin
 61           if dfn[dest]<low[x] then low[x] := dfn[dest];
 62         end;
 63       i := next;
 64     end;
 65   if dfn[x]=low[x] then begin
 66     inc(color);
 67     repeat
 68       u := s[stot];
 69       visit[u] := false;
 70       dec(stot);
 71       col[u] := color;
 72     until u=x;
 73   end;
 74 end;
 75 
 76 procedure main;
 77 var
 78         i: longint;
 79 begin
 80   fillchar(col, sizeof(col), 0);
 81   fillchar(visit, sizeof(visit), 0);
 82   color := 0; time := 0;
 83   for i := 1 to n do
 84   if dfn[i]=0 then tarjan(i);
 85 end;
 86 
 87 procedure sort(b, e: longint);
 88 var
 89         i, j, k: longint;
 90 begin
 91   for i := 1 to e - 1 do
 92     for j := i+1 to e do
 93       if ans[i]>ans[j] then begin
 94         k := ans[i];
 95         ans[i] := ans[j];
 96         ans[j] := k;
 97       end;
 98 end;
 99 
100 procedure print;
101 var
102         i, j, tmp: longint;
103 begin
104   for j := 1 to n do begin
105     tmp := 0;
106     i := vect[j];
107     while i<>0 do
108      with edge[i] do begin
109       if col[dest]=col[j] then begin
110         inc(tmp);
111         ans[tmp] := dest-n;
112       end;
113       i := next;
114     end;
115     sort(1, tmp);
116     write(tmp);
117     for i := 1 to tmp do write(' ', ans[i]);
118     writeln;
119   end;
120 end;
121 
122 begin
123   assign(input,'1.txt'); reset(input);
124   init;
125   main;
126   print;
127 end.