【BZOJ 3661】 Hungry Rabbit （贪心、优先队列）

3661: Hungry Rabbit

Time Limit: 100 Sec Memory Limit: 512 MBSec Special Judge
Submit: 67 Solved: 47

Description

可怕的洪水在夏天不期而至，兔子王国遭遇了前所未有的饥荒，它们不得不去外面的森林里寻找食物。
为了简化起见，我们假设兔子王国中有n只兔子，编号为1n。在救济粮到来之前的m天中，每天恰好有k只兔子需要去森林里寻找粮食。森林里居住着可怕的大灰狼，所幸兔子已经摸清了大灰狼捕食习惯，即狼们在每一天只会捕食特定编号的兔子。为了安全起见，兔子们需要保证每次出去觅食的k只兔子都不会被狼捕食。由于每天出去捕食的兔子都不尽相同，它们为每一天定义了一个生疏度pi，即第i天出来寻找食物，但是第i1天却没有出来觅食的兔子个数。规定第1天的生疏度为0.现在兔子们希望在保证安全的前提下，每天的生疏度不能超过L，请为兔子们构造一个合法的方案。

Input

第一行包括四个整数n,m,k和L.
接下来n行，每行一个长度为m的01串。其中第i行第j个字符若为0，则表示狼在第j天会捕食编号为i的兔子，为1则表示不捕食。

Output

m行，每行k个1-n之间互不相同的整数，代表这一天出去寻找食物的兔子编号。如果没有合法方案，则输出一行1即可。

Sample Input

5 4 3 1
1001
1101
1111
1110
0111

Sample Output

2 3 4
2 3 4
3 4 5
2 3 5

HINT

对于 100% 的测试数据，1 <= n;m <= 800; 1 <= k <= n; 1 <= l <= k

Source

【分析】

　　唉、、、我打了网络流，70分。。。【其实数据弱恰好我数组开小本来90分的。。

　　说说我的网络流打法吧，毕竟想了很久。

　　就是1100011的兔子可以看成两只1100000、0000011的兔子。

　　然后就是说每个兔子表示一个区间，表示它可以从l~r这几天工作。

　　就是要找若干个区间覆盖全区间k次。

　　就类似这样子的建图：

　　拆点那里的点容限制了<=L次交换。反向INF表示区间相交求并集。然后判断是否满流就是否有解。

　　然后有意义的表示区间的边就是答案，输出即可。【好像输出答案有点困难啊？？

　　然后正解是贪心！【表示考场上想过不知道为什么脑抽觉得n^2log过不了？？？【黑人问号？？？

　　就是每次贪心找尽量长的区间。。。

　　有优先队列维护，每次用最优的更新最差的看看是否成立即可。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define Maxn 810

 #define INF 0xfffffff

 struct node

 {

     int l,r,id;

 }t[Maxn*Maxn];

 struct cmp{bool operator()(node x,node y){return x.r<y.r;}};

 struct cmp2{bool operator()(node x,node y){return x.r>y.r;}};

 // bool cmp(node x,node y) {return x.r>y.r;}

 // bool cmp2(node x,node y) {return x.r<y.r;}

 bool cmp3(node x,node y) {return x.l<y.l;}

 priority_queue<node,vector<node>,cmp> q1;

 priority_queue<node,vector<node>,cmp2> q2;

 char s[Maxn];

 bool vis[Maxn];

 int op[Maxn][Maxn];

 int main()

 {

     // int T;

     // scanf("%d",&T);

     // while(T--)

     {

         int n,m,k,l;

         scanf("%d%d%d%d",&n,&m,&k,&l);

         int cnt=,id;

         for(int i=;i<=n;i++)

         {

             scanf("%s",s+);

             for(int j=;j<=m;j++)

             {

                 if((j==||s[j-]=='')&&s[j]=='') id=j;

                 else if(j!=&&s[j-]==''&&s[j]=='') t[++cnt].l=id,t[cnt].r=j-,t[cnt].id=i;

                 if(s[j]==''&&j==m) t[++cnt].l=id,t[cnt].r=m,t[cnt].id=i;

             }

         }

         sort(t+,t++cnt,cmp3);

         // int qz=0;

         while(!q1.empty()) q1.pop();

         while(!q2.empty()) q2.pop();

         int nw=;

         bool ok=;

         memset(vis,,sizeof(vis));

         for(int i=;i<=m;i++)

         {

             int hh=;

             while(t[nw+].l<=i&&nw<cnt) q1.push(t[++nw]);

             while(!q2.empty()&&q2.top().r<i) {vis[q2.top().id]=;q2.pop();}

             while(q2.size()<k)

             {

                 if(q1.empty()||q1.top().r<i) {ok=;break;}

                 vis[q1.top().id]=;

                 q2.push(q1.top());q1.pop();

                 hh++;

                 if(hh>l&&i!=) break;

             }

             if((hh>l&&i!=)||!ok) {ok=;break;}

             while(hh<l&&!q1.empty()&&q1.top().r>q2.top().r)

             {

                 hh++;

                 vis[q2.top().id]=;

                 q2.pop();

                 vis[q1.top().id]=;

                 q2.push(q1.top());q1.pop();

             }

             op[i][]=;

             for(int j=;j<=n;j++) if(vis[j]) op[i][++op[i][]]=j;

         }

         if(!ok) printf("1\n");

         else

         {

             for(int i=;i<=m;i++)

             {

                 for(int j=;j<=op[i][];j++) printf("%d ",op[i][j]);

                 printf("\n");

             }

         }

     }

     return ;

 }

2017-04-24 20:03:42

巴特西

【BZOJ 3661】 Hungry Rabbit （贪心、优先队列）

3661: Hungry Rabbit

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章