bzoj1433:[zjoi2009]假期的宿舍

关键词：

Description

Input

Output

Sample Input

Sample Output

HINT

#include<bits/stdc++.h>
#define RG register
#define il inline
#define db double
#define LL long long
#define N 100000
#define S 0
#define Inf (1<<30)
using namespace std;
struct ed{int nxt,to,c;}e[N];
int head[N],tot,dep[N];
void link(int u,int v,int c){e[tot].nxt=head[u];e[tot].to=v;e[tot].c=c;head[u]=tot++;}
void LINK(int u,int v,int c){link(u,v,c),link(v,u,0);}
int n,BZ[N],cnt,out[N];
void clear(){
  tot=0;memset(head,-1,sizeof(head));
  cnt=0;
}
bool BFS(int s,int t){
  memset(dep,0,sizeof(dep));
  dep[s]=1;queue<int>que;while(!que.empty())que.pop();que.push(s);
  while(!que.empty()){
    int u=que.front();
    que.pop();
    for(int i=head[u];i!=-1;i=e[i].nxt)
      if(!dep[e[i].to]&&e[i].c){
    int v=e[i].to;
    dep[v]=dep[u]+1;
    if(v==t)return true;
    que.push(v);
      }
  }return false;
}
int dinic(int s,int t,int T){
  if(s==t)return T;int tag(0);
  for(int i=head[s];i!=-1;i=e[i].nxt)if(dep[e[i].to]==dep[s]+1&&e[i].c){
      int v=e[i].to;
      int d=dinic(v,t,min(T-tag,e[i].c));
      e[i].c-=d,e[i^1].c+=d,tag+=d;
      if(tag==T)break;
    }if(!tag)dep[s]=0;
  return tag;
}
int maxflow(int s,int t){
  int flow(0);
  while(BFS(s,t))flow+=dinic(s,t,Inf);
  return flow;
}
int main(){
  int T;scanf("%d",&T);
  while(T--){
    clear();
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
      scanf("%d",&BZ[i]);
      LINK(0,i,1);
    }
    for(int i=1;i<=n;++i){
      scanf("%d",&out[i]);
      if(BZ[i])LINK(i+n,2*n+1,1);
      if(BZ[i]&&out[i])cnt++;
    }
    for(int i=1;i<=n;++i){
      if(BZ[i]&&out[i])
      for(int j=1;j<=n;++j){
    int kk;scanf("%d",&kk);
    }
      else {
    LINK(i,i+n,1);
    for(int j=1;j<=n;++j){
      int kk;scanf("%d",&kk);
      if(kk)LINK(i,j+n,1);
    }
      }
    }
    if(maxflow(S,2*n+1)+cnt==n)cout<<"^_^
";
    else cout<<"T_T
";
  }
  return 0;
}

bzoj1433[zjoi2009]假期的宿舍最大流

[ZJOI2009]假期的宿舍TimeLimit:10Sec  MemoryLimit:162MBSubmit:3429  Solved:1459[Submit][Status][Discuss]DescriptionInputOutputSampleInput13110010011100100SampleOutputˆˆHINT对于30 查看详情

bzoj1433[zjoi2009]假期的宿舍（匈牙利）

 1433:[ZJOI2009]假期的宿舍TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 2544  Solved: 1074[Submit][Status][Discuss]DescriptionInputOutputSampleInput13110010011100 查看详情

bzoj1433:[zjoi2009]假期的宿舍

链接bzoj1433:[ZJOI2009]假期的宿舍题解构建二分图，每个人需要住校的人连认识的人的空床和自己的床,匈牙利算法二分图匹配注意清空上组数据ORZ代码#include<cstdio>#include<cstring>#include<algorithm>inlineintread(){intx=0;charc=getchar... 查看详情

bzoj1433:[zjoi2009]假期的宿舍--最大流

1433:[ZJOI2009]假期的宿舍TimeLimit: 10Sec  MemoryLimit: 162MBDescriptionInputOutputSampleInput13110010011100100SampleOutputˆˆHINT对于30%的数据满足1≤n≤12。对于100%的数据满足1≤n≤50 查看详情

[bzoj1433][luogu_p2055][zjoi2009]假期的宿舍

[BZOJ1433][luogu_P2055][ZJOI2009]假期的宿舍试题描述输入输出输入示例13110010011100100输出示例^_^数据规模及约定对于(30 exttt{%})的数据满足(1lenle12)。对于(100 exttt{%})的数据满足(1lenle50,1leTle20)。题解每个人和每个人的床分别建一个节点，... 查看详情

bzoj1433[zjoi2009]假期的宿舍

题意：自行脑补思路：网络流。建模显然，若满流则能够代码：#include<cstdio>#include<cstring>#include<cctype>#include<iostream>#include<algorithm>#include<queue>usingnamespacestd;#defineINF0x3f3f3 查看详情

bzoj1433zjoi2009假期的宿舍

二分图匹配的模板题目，不过建图的时候请细心细心。对了请勿忘记每次的初始化，不然你会爆0.1#include<cstdio>2#include<algorithm>3#include<cstring>4 5boolused[105],bed[233][233];6boolIsStudent[105];7intfa[105],GoHome[105];8in 查看详情

bzoj1433：[zjoi2009]假期的宿舍

明显的二分图最大匹配。#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>#include<bitset>usingnamespacestd;#definerep(i,s,t)for(inti=s;i<=t;i++)#definedwn(i,s,t) 查看详情

bzoj1433:[zjoi2009]假期的宿舍

一道匈牙利的裸题，将床和人建边，纯属复习模版了（然而就是写错了）注意一下0和1的表示。#include<cstdio>#include<cstring>usingnamespacestd;structnode{intx,y,next;}a[41000];intlen,last[2100];voidins(intx,inty){len++;a[len].x=x;a[len]. 查看详情

bzoj1433[zjoi2009]假期的宿舍

题解：二分图建模左边是人，右边是床s向需要在学校的人连边有床的人向t连边认识的人互相连边跑最大流与需要在学校的人数量是否相等比较、#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<vector&... 查看详情

[bzoj1433][zjoi2009]假期的宿舍二分图匹配

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1433首先留在学校的学生向自己的床连边。要住在学校里的人向认识的学生的床连边。跑二分图匹配，看匹配的数量是否等于住在学校的人数。1#include<cstdio>2#include<cstring>3#i... 查看详情

bzoj1433[zjoi2009]假期的宿舍二分图匹配匈牙利算法

原文链接http://www.cnblogs.com/zhouzhendong/p/8372785.html题目传送门-BZOJ1433题解　　我们理一理题目。　　在校的学生，有自己的床，还可以睡朋友的床。　　离校的学生，不占床。　　外来的学生，只能睡朋友的床。　　然后就是一个... 查看详情

bzoj1433:[zjoi2009]假期的宿舍匈牙利算法(代码片段)

i能睡j床的连边(i,j)，跑最大匹配或者最大流，然后看看人数能不能对上总数即可#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintN=1005;intT,n,a[N],b[N],h[N],cnt,con,ans,lk[N],v[N],ti;structqwe 查看详情

1433:[zjoi2009]假期的宿舍(代码片段)

TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 4157  Solved: 1805[Submit][Status][Discuss]Description学校放假了······有些同学回家了，而 查看详情

[zjoi2009]假期的宿舍

1433:[ZJOI2009]假期的宿舍TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 2870  Solved: 1213[Submit][Status][Discuss]DescriptionInputOutputSampleInput13110010011100100Sam 查看详情

bzoj1433

　1433:[ZJOI2009]假期的宿舍TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 3371  Solved: 1425[Submit][Status][Discuss]DescriptionInputOutputSampleInput13110010011100100Sa 查看详情

luogup2055[zjoi2009]假期的宿舍

二次联通门: luoguP2055[ZJOI2009]假期的宿舍    /*luoguP2055[ZJOI2009]假期的宿舍建图时分为两个集合床一个集合人一个集合S到床连边人与自己认识的人连边人与T点连边然后跑最大流判断即可*/#include<algorithm>#include&... 查看详情

zjoi2009假期的宿舍

主要是main()中的处理,接下来就是二分匹配的模板题了#include<cstdio>#include<cstring>#definemaxn110usingnamespacestd;inta[maxn][maxn],link[maxn];intb[maxn],c[maxn];boolvis[maxn];intn,m,cnt,ans,T;boolfind(intx){fo 查看详情