时间限制: 1000ms 内存限制: 65536kB
描述
百度百科有一支神奇的队伍,他们叫自己“百科蝌蚪团”。为了更好的让蝌蚪团的成员们安排工作,百度百科的运营团队定出了一个24小时制的时间表。例如:
1. 每个蝌蚪团成员工作时长相同;
2. 必须安排蝌蚪团成员在他们方便的时间段工作;
3. 蝌蚪团成员安排时间最小安排时间节点(开始工作或停止工作)为半小时,比如04:00或04:30,而不是04:15;
4. 蝌蚪团成员一天在百度百科工作的时间是有上限的,他们会根据自己的情况给出上限。
5. 在特定时间段内必须有一定数量的蝌蚪团成员工作,以保证百度百科不断的进步
请帮运营团队计算一下,能保持24小时稳定在岗的蝌蚪团最少成员的数量。如果有2个蝌蚪团成员工作结束,同时另2个蝌蚪团成员开始工作,这段时间都算有2各成员稳定在岗。
输入
输入有多组,每组测试数据以一个整数N开头(1 ≤ N ≤ 50),表示蝌蚪团的成员数。紧接着,我们会有N个数据块,每一个数据块对应了一名蝌蚪团成员的日程情况。
每个数据块以两个整数开始,分别为K(1 ≤ K ≤ 50)和M(1 ≤ M ≤ 1440),用空格隔开。K表示这个数据块对应蝌蚪团成员方便的时间段的数量,M表示这个成员愿意每天在百度百科工作的最长分钟数。接下去的K行中,每行包括两个时间,分别表示成“HH:MM”的格式,以空格分隔,分别对应了该蝌蚪团成员一个方便的时间段的开始时间、结束时间;例如09:00 10:00表明他在早上九点到十点的时间段是方便的,可以在百度百科工作。如果两个时间相同,则说明这个他全天都是方便的。
最后一组数据的N为0,表示输入结束。
输出
对于每组数据,输出为一个整数,占一行。表示能保持24小时稳定在岗的蝌蚪团最少成员的数量。
样例输入
5
1 720
18:00 12:00
1 1080
00:00 23:00
1 1080
00:00 20:00
1 1050
06:00 00:00
1 360
18:00 00:00
3
1 540
00:00 00:00
3 480
08:00 10:00
09:00 12:00
13:00 19:00
1 420
17:00 00:00
3
1 1440
00:00 00:00
1 720
00:00 12:15
1 720
12:05 00:15
0
样例输出
2
1
1
【题解】
网络流建图。
每半个小时作为一个点,至于建边,我想就很简单了。。。
【代码】
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int oo=200000,N=400;
struct edge
{
int x,y,f,next,op;
}e[20000];
int h[N],d[N],p[N],now[N],num[N],times[N];
bool a[55][55],b[55][1444];
int n,s,t,tot;
void ins(int x,int y,int f)
{
e[++tot].x=x;e[tot].y=y;
e[tot].next=h[x];e[tot].f=f;
h[x]=tot;
e[++tot].x=y;e[tot].y=x;
e[tot].next=h[y];e[tot].f=0;
h[y]=tot;
e[tot].op=tot-1;e[tot-1].op=tot;
}
int isap()
{
int flow=0,aug=oo,u,v,tmp,i,j,ff;
for (i=0;i<=t;i++)
{
d[i]=0;p[i]=-1;
num[i]=0;now[i]=h[i];
}
num[0]=t+1;u=s;
while (d[s]<t+1)
{
for (ff=0,i=now[u];i;i=e[i].next)
{
v=e[i].y;
if (e[i].f && d[u]==d[v]+1)
{
ff=1;
if (e[i].f<aug) aug=e[i].f;
p[v]=i;now[u]=i;
u=v;
if (u==t)
{
flow+=aug;
while (u!=s)
{
j=p[u];
e[j].f-=aug;
e[e[j].op].f+=aug;
u=e[j].x;
}
aug=oo;
}
break;
}
}
if (ff) continue;
num[d[u]]--;
if (!num[d[u]]) return flow;
tmp=t+1;
for (i=h[u];i;i=e[i].next)
{
v=e[i].y;
if (e[i].f && d[v]<tmp)
{
tmp=d[v];now[u]=i;
}
}
d[u]=tmp+1;
num[d[u]]++;
if (u!=s) u=e[p[u]].x;
}
return flow;
}
void build(int x)
{
int i,j;
s=0;t=n+97;
memset(h,0,sizeof(h));
tot=0;
for (i=1;i<=n;i++)
ins(s,i,times[i]);
for (i=1;i<=n;i++)
for (j=0;j<48;j++)
if (a[i][j])
ins(i,n+j+1,1);
for (i=0;i<48;i++)
ins(n+i+1,n+49+i,x);
for (i=0;i<48;i++)
ins(n+49+i,t,x);
}
void fill(int id,int x,int y)
{
for (int i=x;i<y;i++)
b[id][i]=true;
}
int main()
{
freopen("in.txt","r",stdin);
//freopen("ou.txt","w",stdout);
int i,j,k;
while (cin >> n)
{
if (n==0) break;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for (i=1;i<=n;i++)
{
int ss;
cin >> ss >> times[i];
times[i]/=30;
for (j=1;j<=ss;j++)
{
int aa,bb,cc,dd,t1,t2;
scanf("%d:%d %d:%d\n",&aa,&bb,&cc,&dd);
t1=aa*60+bb;
t2=cc*60+dd;
if (t1==t2) fill(i,0,1440);
else if (t1<t2) fill(i,t1,t2);
else
{
fill(i,t1,1440);fill(i,0,t2);
}
}
}
for (i=1;i<=n;i++)
for (j=0;j<48;j++)
{
bool ff=true;
for (k=j*30;k<j*30+30;k++)
if (!b[i][k]) ff=false;
a[i][j]=ff;
}
for (i=n;i;i--)
{
build(i);
int tmp=isap();
if (tmp>=i*48) break;
}
cout << i << endl;
}
}
分享到:
相关推荐
百度百科有一支神奇的队伍,他们叫自己“百科蝌蚪团”。为了更好的让蝌蚪团的成员们安排工作,百度百科的运营团队定出了一个24小时制的时间表。例如: 1. 每个蝌蚪团成员工作时长相同; 2. 必须安排蝌蚪团成员在他们...
百度之星2012 F题 百科蝌蚪团 答案 代码 来源POJ 测试代码,我也不知道为什么。老题
主题早操:小蝌蚪找妈妈.pdf
中班音乐教案:小蝌蚪音乐家.doc
表演游戏:小蝌蚪找妈妈定义.pdf
一年级语文:小蝌蚪找妈妈教学设计及反思.pdf
幼儿园教案2021-中班音乐教案:小蝌蚪音乐家.doc
幼儿园教案2021-中班美术:可爱的蝌蚪宝宝(美工).doc
幼儿园教案2021-图画:小蝌蚪找妈妈(中班美工).doc
【创意幼教】最新幼儿园中班音乐游戏活动教案:小蝌蚪教案教案附教学反思(四篇).pdf
小蝌蚪鼠标指针是一款可爱风格的鼠标指针主题包,一只迷你小蝌蚪在你的桌面上翻转、回旋是不是很有趣呢,快来下载小蝌蚪鼠标指针让你的电脑桌面更加生动有趣。 使用安装: 只需要选择AutoSetup.inf文件单击右键,在...
微信小程序源码-小工具类:蝌蚪签到
大班手印画教案:青蛙和蝌蚪.docx
科学活动:有趣的蝌蚪(中班).doc
幼儿园教案2021-科学活动:有趣的蝌蚪(中班).doc
第一名的小蝌蚪 小蝌蚪,高级前端工程师。 2019:保密2018:阿里淘宝技术部2013〜2017:阿里移动事业部 2020年心路历程 2019年心路历程 交流 欢迎关注我的微信公众号,微信扫下二维码或搜索“前端屌丝”,发现了一个...
小蝌蚪阅读器 v2.2更新内容: 刷新去重、改进排版。 小蝌蚪阅读器是一款TXT文件阅读工具,风格多样,使用方便。 小蝌蚪阅读器功能: 1.版面舒适,长时间阅读不花眼、不干涩畏光。 视觉去沙漠化的背景水印图; 字符...
小蝌蚪视频6.0.0.apk
【创意幼教】最新幼儿园大班美术活动教案:可爱的小蝌蚪教案附教学反思(四篇).pdf