首页 > ACM题库 > HDU-杭电 > HDU 3121-FreeOpen-分治-[解题报告]HOJ
2014
03-03

HDU 3121-FreeOpen-分治-[解题报告]HOJ

FreeOpen

问题描述 :

FreeOpen is an organization which arranges blind data for girls and boys. The moral of that name is “Open your free mind to find your other half”. FreeOpen use a pet to make a match to a girl and a boy. FreeOpen believe that if a girl and a boy like each other and they like the same pet, they will be happy when they are living together with that pet.
There are n boys, m girls and k pets. FreeOpen want know the maximum matches. Each match consists of one girl, one boy and one pet, and each girl, boy or pet can only be in one single match.

输入:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers G, B, P, indicating the number of girls, the number of boys and the number of pets. The next G * B matrix indicates whether a girl and a boy like each other. The i-th girl and j-th boy like each other if and only if Matrix (i, j) = 1; the next G * P matrix indicates whether a girl likes a pet and the next B * P matrix indicates whether a boy likes a pet.

输出:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers G, B, P, indicating the number of girls, the number of boys and the number of pets. The next G * B matrix indicates whether a girl and a boy like each other. The i-th girl and j-th boy like each other if and only if Matrix (i, j) = 1; the next G * P matrix indicates whether a girl likes a pet and the next B * P matrix indicates whether a boy likes a pet.

样例输入:

2
2 1 3
1
1
1 1 1
1 1 1
0 0 0
15 15 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

样例输出:

0
13

被这题整整搞了两天啊,先是官方题解:

Freeopen
标程做法是IDA* H函数为三次二分图匹配. 搜索顺序按度来优化.
这个题生成数据的时候光在关注怎么卡掉一般的搜索了.写了六七个搜索,分别用十个数据让这几个搜索超时.
但是数据量太少了,导致有一些莫名其妙的网络流AC了.
此题是npc问题,可以划归到3-sat.所以应该不存在多项式算法.

  

话说这题数据确实太烂了,这种题目单靠手造数据很难卡掉所有非标程做法的,不但没卡掉别的方法,按标程方法不加强减枝也很难过掉了

话说过来用这题来练习IDA*和搜索减枝确实不错,一般的IDA*是从少层向多层去搜,这题求最大值,就要IDA*从多向少去搜了,构造h()函数要满足大于等于实际值,从多到少的IDA*并不是一个很实用的方法,层数越多搜到的状态数越多,就像IDA*用二分更慢一样,不过这也是一种IDA*新的使用方法,偶尔会派上用场吧。

因为这题看起来就和二分匹配很有关系(我可以保证如果比赛时遇到这题我绝对不会向搜索方向去想,或许是二分匹配变形或是网络流什么的),如果想到A*搜索的话用二分图匹配也正常,三次二分图匹配作为A*函数是很大胆的一种做法,这么高复杂度的算法用在频繁调用的h()中就必须要保证他的减枝的有效性。三次二分匹配分别做女生和男生,女生和宠物,男生和宠物,取最小值(多次数据测试证明,第一次二分匹配会使速度变慢),如果这个值加上步数小于上限则跳出。

至于按度优化没什么可说的,只要不按正序基本都能过了,按度反序都能过的 = =||,我更不会告诉你,按照输入顺序反序15ms哦~~

然后就是各种减枝了…

  

写了好久的代码,但由于能力有限,效率很低,500+ms,由于数据问题,可能改一个很小的,甚至无关的地方都可能使时间突变…

#include<cstdio>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 #define MIN(x,y) (x<y?x:y)
 
 int g,b,p;
 int G,B,P;
 int gdeg[22];
 int grank[22];
 int gb[22],gp[22],bp[22];
 bool in(){
     char c=getchar();
     while(c<=32) c=getchar();
     return (c=='1');
 }
 
 int vis;
 int mat[22];
 inline bool find0(int u){
     for(int i=0;i<b;i++){
         if(B&(1<<i)) continue;
         if(!(gb[u]&(1<<i))) continue;
         if(vis&(1<<i)) continue;
         vis|=(1<<i);
         if(mat[i]==-1||find0(mat[i])){
             mat[i]=u;
             return true;
         }
     }
     return false;
 }
 
 inline bool find1(int u){
     for(int i=0;i<p;i++){
         if(P&(1<<i)) continue;
         if(!(gp[u]&(1<<i))) continue;
         if(vis&(1<<i)) continue;
         vis|=(1<<i);
         if(mat[i]==-1||find1(mat[i])){
             mat[i]=u;
             return true;
         }
     }
     return false;
 }
 
 inline bool find2(int u){
     for(int i=0;i<p;i++){
         if(P&(1<<i)) continue;
         if(!(bp[u]&(1<<i))) continue;
         if(vis&(1<<i)) continue;
         vis|=(1<<i);
         if(mat[i]==-1||find2(mat[i])){
             mat[i]=u;
             return true;
         }
     }
     return false;
 }
 
 int dep;
 inline bool h(int d,int tg){
     int cnt=0;
     memset(mat,-1,sizeof(mat));
     for(int i=tg;i<g;i++){
         vis=0;
         if(find0(grank[i])) cnt++;
         if(cnt>dep-d) break;
     }
     if(cnt+d<dep) return false;
     
     cnt=0;
     memset(mat,-1,sizeof(mat));
     for(int i=tg;i<g;i++){
         vis=0;
         if(find1(grank[i])) cnt++;
         if(cnt>dep-d) break;
     }
     if(cnt+d<dep) return false;
     
     cnt=0;
     memset(mat,-1,sizeof(mat));
     for(int i=0;i<b;i++){
         if(B&(1<<i)) continue;
         vis=0;
         if(find2(i)) cnt++;
         if(cnt>dep-d) break;
     }
     if(cnt+d<dep) return false;
     
     return true;
 }
 
 bool dfs(int d,int tg){
     if(d==dep) return true;
     if(!h(d,tg)) return false;
     
     for(int ii=tg;ii<g;ii++){
         int i=grank[ii];
         G|=(1<<i);
         for(int j=0;j<b;j++){
             if(B&(1<<j)) continue;
             if(!(gb[i]&(1<<j))) continue;
             B|=(1<<j);
             for(int k=0;k<p;k++){
                 if(P&(1<<k)) continue;
                 if(gp[i]&bp[j]&(1<<k)){
                     P|=(1<<k);
                     if(dfs(d+1,ii+1)) return true;
                     P^=(1<<k);
                 }
             }
             B^=(1<<j);
         }
         G^=(1<<i);
     }
     return false;
 }
 
 bool gcmp(const int& a,const int& b){
     return gdeg[a]<gdeg[b];
 }
 
 int main(){
     int t;
     scanf("%d",&t);
     while(t--){
         scanf("%d%d%d",&g,&b,&p);
         memset(gb,0,sizeof(gb));
         memset(gp,0,sizeof(gp));
         memset(bp,0,sizeof(bp));
         memset(gdeg,0,sizeof(gdeg));
         for(int i=0;i<g;i++){
             for(int j=0;j<b;j++){
                 gb[i]|=(in()<<j);
             }
         }
         for(int i=0;i<g;i++){
             for(int j=0;j<p;j++){
                 gp[i]|=(in()<<j);
             }
         }
         for(int i=0;i<b;i++){
             for(int j=0;j<p;j++){
                 bp[i]|=(in()<<j);
             }
         }
         
         for(int i=0;i<g;i++){
             grank[i]=i;
             for(int j=0;j<b;j++){
                 if(!(gp[i]&bp[j])) gb[i]&=~(1<<j);
                 if(gb[i]&(1<<j)) gdeg[i]++;
             }
         }
         sort(grank,grank+g,gcmp);
         //reverse(grank,grank+g);
         
         G=B=P=0;
         dep=MIN(MIN(g,b),p);
         while(true){
             if(dfs(0,0)) break;
             dep--;
         }
         
         printf("%d\n",dep);
     }
 }

  


参考:http://www.cnblogs.com/ambition/archive/2011/08/25/FreeOpen.html


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.