`
tulunta
  • 浏览: 356817 次
文章分类
社区版块
存档分类
最新评论

【百度之星资格赛】F:百科蝌蚪团

 
阅读更多

F:百科蝌蚪团

时间限制: 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;
    }
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics