貌似弃坑了的样子...QAQ...其实并没有啊...

一到暑假就颓废了QAQ...懒得写博客...所以还是来补一补吧...

题目就不贴了，直接bzoj看吧...

题目大意：  一个学校里有n个人, 有 几个是学生，剩下的是拜访的，这些学生中，有几个要回家，有几个不回家要在学校过夜，然后拜访的也要在学校过夜。可是每一个人只睡他认识的人......的床。问是否有一个方案使得这些不回家的学生和拜访都能睡到床。

思路：难得的最大流裸题吧...毕竟很少有自己能一眼的了...很显然可以这样做：

对于每一个人，建一个点x，同时建多一个点xx，表示他们对应的床。当然拜访学生是没有床的，但是我为了方便建了。

 源点和每一个人的点x连一条边，如果这个人是不回家的学生或者是拜访的人，辣么流量为 1 表示这是需要床的人 否则为 0 表示这是不需要床的人...这个流量为0的边要建，不然貌似会在分层的时候炸...QAQ...

然后汇点和每一个人的点xx连一条边，如果这个人是学生，辣么流量为 1 表示有床，否则为0 表示没有床，一样，流量为0的边要建。

然后如果 人 i  认识 人 j ...辣么 人 i 的就可以睡人 j .......的床（不要问我为什么要把人和床分开一点...手动滑稽）。所以就 人 i 的 点x 和人 j 的点xx 连一条边 流量 1

 因为这个所以 每个人的点 x 要和 xx 连一条流量1的边

某些坑点？（也许并不是，只是我傻了没看到，所以wa了一次）

提一下吧：

这个随机的数有可能是1或0所以还是不要偷懒乖乖特判是否学生

然后就给代码吧：

1 type  2   node=record  3       x,y:longint;  4       flow:longint;  5       next:longint;  6   end;  7 var first,dis,a:array[0..150]of longint;  8     q:array[0..100000]of longint;  9     n,tot,p,t:longint; 10     i,j:longint; 11     e:array[0..100000]of node; 12     ans,sum:longint; 13     x,y,z:longint; 14 function bfs(s,t:longint):boolean; 15 var head,tail:longint; 16     i,now,y:longint; 17 begin 18   head:=1; 19   tail:=1; 20   for i:=0 to p do 21   dis[i]:=-1; 22   q[1]:=s; 23   dis[s]:=0; 24   while head<=tail do 25   begin 26     now:=q[head]; 27     i:=first[now]; 28     while i<>-1 do 29     begin 30       y:=e[i].y; 31       if (dis[y]<0)and(e[i].flow>0) then 32       begin 33         dis[y]:=dis[now]+1; 34         inc(tail); 35         q[tail]:=y; 36       end; 37       i:=e[i].next; 38     end; 39     inc(head); 40   end; 41   if dis[t]=-1 then exit(false) else exit(true); 42 end; 43 procedure adde(x,y,f:longint); 44 begin 45   e[tot].next:=first[x]; 46   e[tot].x:=x; 47   e[tot].y:=y; 48   e[tot].flow:=f; 49   first[x]:=tot; 50   inc(tot); 51 end; 52 function dfs(x,mx:longint):longint; 53 var i,k:longint; 54 begin 55   if x=p then exit(mx); 56   i:=first[x]; 57   while i<>-1 do 58   begin 59     y:=e[i].y; 60     if (e[i].flow>0)and(dis[y]=dis[x]+1) then 61     begin 62       if e[i].flow>mx then k:=dfs(y,mx) else k:=dfs(y,e[i].flow); 63       dec(e[i].flow,k); 64       inc(e[i xor 1].flow,k); 65       if k>0 then exit(k); 66     end; 67     i:=e[i].next; 68   end; 69   exit(0); 70 end; 71 begin 72   read(t); 73   while t>0 do 74   begin 75     fillchar(e,sizeof(e),0); 76     dec(t); 77     read(n); 78     p:=2*n+1; 79     ans:=0; 80     sum:=0; 81     tot:=0; 82     for i:=0 to p do 83     first[i]:=-1; 84     for i:=1 to n do 85     begin 86       read(a[i]); 87       if a[i]=1 then 88       begin 89         adde(i+n,p,1); 90         adde(p,i+n,0); 91       end else 92       begin 93         adde(i+n,p,0); 94         adde(p,i+n,0); 95         inc(sum); 96       end; 97     end; 98     for i:=1 to n do 99     begin100       read(x);101       if a[i]=0 then102       begin103         adde(0,i,1);104         adde(i,0,0);105       end else106       begin107         if x=0 then108         begin109           adde(0,i,1);110           adde(i,0,0);111           inc(sum);112         end else113         begin114           adde(0,i,0);115           adde(i,0,0);116         end;117       end;118     end;119     for i:=1 to n do120       for j:=1 to n do121       begin122         read(x);123         if (x=1)or(i=j) then124         begin125           adde(i,n+j,1);126           adde(n+j,i,0);127         end;128       end;129     while bfs(0,p) do130     begin131       repeat132         z:=dfs(0,1 << 25);133         inc(ans,z);134       until z>0;135     end;136     if ans>=sum then writeln('^_^') else writeln('T_T');137   end;138 end.

pascal代码应该很好看的吧...要c++的没有...>_<