程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4735 DLX爆搜

HDU 4735 DLX爆搜

編輯：C++入門知識

Little Wish~ lyrical step~

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 417 Accepted Submission(s): 109

Problem Description N children are living in a tree with exactly N nodes, on each node there lies either a boy or a girl.
A girl is said to be protected, if the distance between the girl and her nearest boy is no more than D.
You want to do something good, so that each girl on the tree will be protected. On each step, you can choose two nodes, and swap the children living on them.
What is the minimum number of steps you have to take to fulfill your wish?
Input The first line has a number T (T <= 150) , indicating the number of test cases.
In a case, the first line contain two number n (1 <= n <= 50), D (1 <= D <= 10000000), Which means the number of the node and the distance between the girls and boys.
The next lines contains n number. The i_th number means the i_th node contains a girl or a boy. (0 means girl 1 means boy), The follow n - 1 lines contains a, b, w, means a edge connect a_th node and b_th node, and the length of the edge is w (1 <= w <= 10000000).
Output For every case, you should output "Case #t: " at first, without quotes. The t is the case number starting from 1.
Then follows the answer, -1 meas you can't comlete it, and others means the minimum number of the times.
Sample Input

Sample Output

Case #1: 1

Source 2013 ACM/ICPC Asia Regional Chengdu Online

一棵樹n個節點，每一個節點或者有男孩，或者有女孩，每一個男孩可以保護距離他D范圍之內的男孩，問最少通過多少次交換可以使得所有女孩受到保護。

男孩與男孩，女孩與女孩之間的交換顯然毫無意義，只用考慮男孩與女孩之間的交換，可以DP做，也可以DLX爆搜，只考慮男孩，女孩毫無意義，可以先DLX爆搜得到解，然後判斷需要多少次交換，當搜到一組解時，裡面的女孩個數就是需要交換的次數，我們只需要把女孩全部移走，換成男孩，就可以保證把所有點覆蓋。

代碼：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/1 22:56:26
File Name :12.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
int boys,boy[100],d[60][60];
struct DLX{
    const static int maxn=7500;
    #define FF(i,A,s) for(int i = A[s];i != s;i = A[i])
    int L[maxn],R[maxn],U[maxn],D[maxn];
    int size,col[maxn],row[maxn],s[maxn],H[100];
    bool vis[100];
	int ans[maxn],cnt;
    void init(int m){
        for(int i=0;i<=m;i++){
            L[i]=i-1;R[i]=i+1;U[i]=D[i]=i;s[i]=0;
        }
        memset(H,-1,sizeof(H));
        L[0]=m;R[m]=0;size=m+1;
    }
	void link(int r,int c){
         U[size]=c;D[size]=D[c];U[D[c]]=size;D[c]=size;
         if(H[r]<0)H[r]=L[size]=R[size]=size;
         else {
             L[size]=H[r];R[size]=R[H[r]];
             L[R[H[r]]]=size;R[H[r]]=size;
         }
         s[c]++;col[size]=c;row[size]=r;size++;
     }
	void del(int c){//精確覆蓋
        L[R[c]]=L[c];R[L[c]]=R[c];  
        FF(i,D,c)FF(j,R,i)U[D[j]]=U[j],D[U[j]]=D[j],--s[col[j]];  
    }  
    void add(int c){  //精確覆蓋
        R[L[c]]=L[R[c]]=c;  
        FF(i,U,c)FF(j,L,i)++s[col[U[D[j]]=D[U[j]]=j]];  
    }  
	bool dfs(int k){//精確覆蓋
        if(!R[0]){  
            cnt=k;return 1;  
        }  
        int c=R[0];FF(i,R,0)if(s[c]>s[i])c=i;  
        del(c);  
        FF(i,D,c){  
            FF(j,R,i)del(col[j]);  
            ans[k]=row[i];if(dfs(k+1))return true;  
            FF(j,L,i)add(col[j]);  
        }  
        add(c);  
        return 0;
    }  
    void remove(int c){//重復覆蓋
        FF(i,D,c)L[R[i]]=L[i],R[L[i]]=R[i];
    }
     void resume(int c){//重復覆蓋
         FF(i,U,c)L[R[i]]=R[L[i]]=i;
     }
    int A(){//估價函數
        int res=0;
        memset(vis,0,sizeof(vis));
        FF(i,R,0)if(!vis[i]){
                res++;vis[i]=1;
                FF(j,D,i)FF(k,R,j)vis[col[k]]=1;
            }
        return res;
    }
    void dfs(int now,int &lim){//重復覆蓋
		if(now+A()>boys)return;int tt=0;
		for(int i=0;i=lim)return;
		if(!R[0]){
			lim=now-tt;
			return;
		}
        int temp=INF,c;
        FF(i,R,0)if(temp>=s[i])temp=s[i],c=i;
        FF(i,D,c){
			ans[now]=row[i];
            remove(i);FF(j,R,i)remove(j);
            dfs(now+1,lim);
            FF(j,L,i)resume(j);resume(i);
        }
    }
}dlx;

int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int T;
	 cin>>T;
	 for(int t=1;t<=T;t++){
		 int n,D;boys=0;
		 scanf("%d%d",&n,&D);
		 dlx.init(n);
		 for(int i=1;i<=n;i++)scanf("%d",&boy[i]),boys+=boy[i];
		 for(int i=1;i<=n;i++)
			 for(int j=1;j<=n;j++)
				 d[i][j]=i==j?0:INF;
		 for(int i=1;id[i][k]+d[k][j])d[i][j]=d[i][k]+d[k][j];
		 for(int i=1;i<=n;i++)
			 for(int j=1;j<=n;j++)
				 if(d[i][j]<=D)dlx.link(i,j);
		 int ans=INF;
		 dlx.dfs(0,ans);
		 if(ans>boys)ans=-1;
		 printf("Case #%d: %d\n",t,ans);
	 }
     return 0;
}