关键词:
1433: [ZJOI2009]假期的宿舍
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 2286 Solved: 969
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0
Sample Output
HINT
对于30% 的数据满足1 ≤ n ≤ 12。
对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 55;
int T,a[maxn][maxn],vis[maxn],ans,bed[maxn],people[maxn],pipei[maxn],n,panduan[maxn],cnt1,cnt2;
bool xiongyali(int x)
{
for (int i = 1; i <= cnt1; i++)
if (a[x][bed[i]] && !vis[bed[i]])
{
vis[bed[i]] = 1;
if (!pipei[bed[i]] || xiongyali(pipei[bed[i]]))
{
pipei[bed[i]] = x;
return true;
}
}
return false;
}
int main()
{
scanf("%d", &T);
while (T--)
{
ans = 0;
memset(a, 0, sizeof(a));
memset(bed, 0, sizeof(bed));
memset(panduan, 0, sizeof(panduan));
memset(people, 0, sizeof(people));
memset(pipei, 0, sizeof(pipei));
cnt1 = cnt2 = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &panduan[i]);
for (int i = 1; i <= n; i++)
{
int temp;
scanf("%d", &temp);
if (panduan[i])
{
if (temp)
bed[++cnt1] = i;
else
people[++cnt2] = bed[++cnt1] = i;
}
else
people[++cnt2] = i;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i++)
if (panduan[i])
a[i][i] = 1;
for (int i = 1; i <= cnt2; i++)
{
memset(vis, 0, sizeof(vis));
if (xiongyali(people[i]))
ans++;
}
if (cnt2 > cnt1)
ans = -1;
if (ans == cnt2)
printf("^_^
");
else
printf("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 查看详情