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
1 #include <stdio.h> 2 #include <memory.h> 3 #include <stdlib.h> 4 #define maxn 102 5 int d[maxn],g[maxn][maxn],f[maxn][maxn],pre[maxn],map[maxn][maxn],sum[maxn],current[maxn]; 6 int n,m,num,mm; 7 struct node 8 { 9 int x,y; 10 }seg[1000],time[1000]; 11 #define oo 0xfffffff 12 int cmp(const void *a,const void *b) 13 { 14 struct node *va=(struct node*)a; 15 struct node *vb=(struct node*)b; 16 return va->x-vb->x; 17 } 18 void rev_bfs(int t) 19 { 20 int queue[maxn],flag[maxn]; 21 int head,tail,i; 22 memset(sum,0,sizeof(sum)); 23 for (i=0;i<=n+49;i++) 24 { 25 d[i]=n+49; 26 sum[n+49]++; 27 } 28 sum[n+49]--; 29 sum[0]++; 30 d[t]=0; 31 queue[1]=t; 32 flag[t]=1; 33 head=1;tail=1; 34 memset(flag,0,sizeof(flag)); 35 while (head<=tail) 36 { 37 for (i=0;i<=n+49;i++) 38 if (flag[i]==0&&g[i][queue[head]]>0) 39 { 40 queue[++tail]=i; 41 d[i]=d[queue[head]]+1; 42 sum[n+49]--; 43 sum[d[i]]++; 44 flag[i]=1; 45 } 46 head++; 47 } 48 } 49 void augment(int s,int t) 50 { 51 int i,min; 52 min=oo; 53 for (i=t;i!=s;i=pre[i]) 54 if (g[pre[i]][i]<min) 55 min=g[pre[i]][i]; 56 for (i=t;i!=s;i=pre[i]) 57 { 58 g[pre[i]][i]-=min;; 59 g[i][pre[i]]+=min; 60 f[pre[i]][i]+=min; 61 f[i][pre[i]]-=min; 62 } 63 } 64 int retreat(int *u,int s) 65 { 66 int v,min; 67 min=n+49; 68 for (v=0;v<=n+49;v++) 69 if (g[*u][v]>0&&d[v]<min) 70 min=d[v]; 71 sum[d[*u]]--; 72 if ((sum[d[*u]])==0&&d[*u]<=n+49) return 0; 73 d[*u]=min+1; 74 sum[d[*u]]++; 75 current[*u]=0; 76 if (*u!=s) *u=pre[*u]; 77 return 1; 78 } 79 void ISAP(int s,int t) 80 { 81 int u,v; 82 rev_bfs(t); 83 u=s; 84 while (d[s]<n+50) 85 { 86 for (v=current[u];v<=n+49;v++) 87 if (g[u][v]>0&&d[u]==d[v]+1) 88 break; 89 if (v<=n+49) 90 { 91 current[u]=v; 92 pre[v]=u; 93 u=v; 94 if (u==t) 95 { 96 augment(s,t); 97 u=s; 98 } 99 } 100 else if (retreat(&u,s)==0) return; 101 } 102 } 103 void init() 104 { 105 int i,j,a,b,c,d,min,t,k,ans,max,st,en,temp; 106 while (scanf("%d",&n)!=EOF&&n) 107 { 108 memset(map,0,sizeof(map));; 109 for (i=1;i<=n;i++) 110 { 111 scanf("%d%d",&m,&t); 112 map[48][i+48]=t/30; 113 num=0; 114 mm=0; 115 for (j=1;j<=m;j++) 116 { 117 scanf("%d:%d %d:%d",&a,&b,&c,&d); 118 if (a==c&&b==d) 119 { 120 for (k=0;k<48;k++) 121 map[i+48][k]=1; 122 continue; 123 } 124 if (c==0&&d==0) 125 { 126 num++; 127 seg[num].x=a*60+b; 128 seg[num].y=1440; 129 } 130 else if (a*60+b>c*60+d) 131 { 132 num++; 133 seg[num].x=a*60+b; 134 seg[num].y=1440; 135 num++; 136 seg[num].x=0; 137 seg[num].y=c*60+d; 138 } 139 else 140 { 141 num++; 142 seg[num].x=a*60+b; 143 seg[num].y=c*60+d; 144 } 145 } 146 if (num==0) continue; 147 qsort(seg+1,num,sizeof(seg[1]),cmp); 148 st=seg[1].x;en=seg[1].y; 149 seg[num+1].x=1500;seg[num+1].y=1600; 150 for (j=2;j<=num+1;j++) 151 { 152 a=seg[j].x; 153 b=seg[j].y; 154 if (st<=a&&a<=en&&en<b) 155 en=b; 156 else if (a>en) 157 { 158 mm++; 159 time[mm].x=st; 160 time[mm].y=en; 161 st=a; 162 en=b; 163 } 164 } 165 for (j=1;j<=mm;j++) 166 { 167 a=time[j].x/60; 168 b=time[j].x-60*a; 169 c=time[j].y/60; 170 d=time[j].y-60*c; 171 if (a==c) 172 { 173 if (b==0&&d>=30) 174 map[i+48][a*2]=1; 175 } 176 else 177 { 178 if (b>0&&b<=30) b=30; 179 if (b>30) 180 { 181 a++; 182 b=0; 183 } 184 if (d<30) d=0; 185 if (d>30) d=30; 186 while (a!=c||b!=d) 187 { 188 map[i+48][a*2+b/30]=1; 189 b+=30; 190 if (b==60) 191 { 192 a++; 193 b=0; 194 } 195 } 196 } 197 } 198 } 199 max=oo; 200 for (j=0;j<48;j++) 201 { 202 temp=0; 203 for (k=49;k<n+49;k++) 204 if (map[k][j]>0) temp++; 205 if (temp<max) 206 max=temp; 207 } 208 ans=0; 209 for (j=1;j<=max;j++) 210 { 211 memset(g,0,sizeof(g)); 212 memset(f,0,sizeof(f)); 213 memset(current,0,sizeof(current)); 214 for (i=0;i<=49+n;i++) 215 for (k=0;k<=49+n;k++) 216 g[i][k]=map[i][k]; 217 for (i=0;i<48;i++) 218 g[i][n+49]=j; 219 ISAP(48,n+49); 220 min=oo; 221 for (i=0;i<48;i++) 222 if (f[i][n+49]<min) 223 min=f[i][n+49]; 224 if (min>ans) ans=min; 225 } 226 printf("%d\n",ans); 227 } 228 } 229 int main() 230 { 231 init(); 232 return 0; 233 } 234 235