HDU 4735 Little Wish~ lyrical step~（DLX , 反复覆盖）

解题思路：

DLX 的模板题。反复覆盖。

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

#define FOR(i,x,y) for(int i=x;i<=y;i++)

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 7500;

int boys , boy[100];

struct DLX

{

    #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 Dance(int now, int &lim)

    {

		if(now + A() > boys) return ; int tt = 0;

		for(int i=0;i<now;i++)tt += boy[ans[i]];

		if(now - tt >= 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);

            Dance(now + 1, lim);

            FF(j, L, i)resume(j);resume(i);

        }

    }

}dlx;

int N , D;

int d[100][100];

int main()

{

	int T , kcase = 1;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d%d", &N, &D);dlx.init(N);

		boys = 0; FOR(i, 1, N) scanf("%d", &boy[i]) , boys += boy[i];

		FOR(i, 1, N) FOR(j, 1, N) d[i][j] = (i == j ? 0 : INF);

		FOR(i, 1, N-1)

		{

			int u , v , w;

			scanf("%d%d%d",&u,&v,&w);

			d[u][v] = d[v][u] = w;

		}

		FOR(k, 1, N)

		FOR(i, 1, N)

		FOR(j, 1, N)

			if(d[i][j] > d[i][k] + d[k][j])

				d[i][j] = d[i][k] + d[k][j];

		FOR(i, 1, N) FOR(j, 1, N)

		if(d[i][j] <= D) dlx.link(i, j);

		int ans = INF;

		dlx.Dance(0, ans);

		if(ans > boys) ans = -1;

		printf("Case #%d: %d\n", kcase++, ans);

	}

	return 0;

}