HDU 4735 Little Wish~ lyrical step~

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

1

3 1

0 0 1

1 2 1

1 3 1

Sample Output

Case #1: 1

floyd算出全部最短路，然後建圖跑dlx重複覆寫

#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn = 55;
int T, n, m, x, y, z, t, X, Y,tot,f[maxn][maxn],tt=0;

inline void read(int &ret)
{
	char c;
	do {
		c = getchar();
	} while (c < '0' || c > '9');
	ret = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
}

struct DLX
{
	#define maxn 500005
	#define F(i,A,s) for (int i=A[s];i!=s;i=A[i])
	int L[maxn], R[maxn], U[maxn], D[maxn];
	int row[maxn], col[maxn], ans[maxn], cnt[maxn];
	int n, m, num, sz;

	void add(int now, int l, int r, int u, int d, int x, int y)
	{
		L[now] = l;	R[now] = r;	U[now] = u;
		D[now] = d;   row[now] = x;  col[now] = y;
	}
	void reset(int n, int m)
	{
		num = 0x7FFFFFFF;
		this->n = n;	this->m = m;
		for (int i = 0; i <= m; i++)
		{
			add(i, i - 1, i + 1, i, i, 0, i);
			cnt[i] = 0;
		}
		L[0] = m; 	R[m] = 0; 	sz = m + 1;
	}
	void insert(int x, int y)
	{
		int ft = sz - 1;
		if (row[ft] != x)
		{
			add(sz, sz, sz, U[y], y, x, y);
			U[D[sz]] = sz; D[U[sz]] = sz;
		}
		else
		{
			add(sz, ft, R[ft], U[y], y, x, y);
			R[L[sz]] = sz; L[R[sz]] = sz;
			U[D[sz]] = sz; D[U[sz]] = sz;
		}
		++cnt[y];	++sz;
	}

	//精确覆寫
	void remove(int now)
	{
		R[L[now]] = R[now];
		L[R[now]] = L[now];
		F(i, D, now) F(j, R, i)
		{
			D[U[j]] = D[j];
			U[D[j]] = U[j];
			--cnt[col[j]];
		}
	}
	void resume(int now)
	{
		F(i, U, now)	F(j, L, i)
		{
			D[U[j]] = j;
			U[D[j]] = j;
			++cnt[col[j]];
		}
		R[L[now]] = now;
		L[R[now]] = now;
	}
	bool dfs(int x)
	{
		//if (x + A() >= num) return;
		if (x==n) { num = min(num, x); return true; }
		int now = R[0];
		if (now>n) return false;
		for (int i=R[0];i<=n;i=R[i]) if (cnt[now]>cnt[i]) now = i;
		remove(now);
		F(i, D, now)
		{
			ans[x] = row[i];
			F(j, R, i) remove(col[j]);
			if (dfs(x + 1)) return true;
			F(j, L, i) resume(col[j]);
		}
		resume(now);
		return false;
	}
	//精确覆寫

	//重複覆寫
	void Remove(int now)
	{
		F(i, D, now)
		{
			L[R[i]] = L[i];
			R[L[i]] = R[i];
		}
	}
	void Resume(int now)
	{
		F(i, U, now) L[R[i]] = R[L[i]] = i;
	}
	int vis[maxn];
	int flag[maxn];
	int A()
	{
		int dis = 0;
		F(i, R, 0) vis[i]=0;
		F(i, R, 0) if (!vis[i]) 
		{
			vis[i]=1;
			dis++;
			F(j, D, i) F(k, R ,j) vis[col[k]]=1;
		}
		return dis;
	}
	void Dfs(int x,int y,int z)
	{
		if (!R[0]) num = max(num, y+z-x);
		else if (x==z) return;
		else if (y+z-x>num&&A()+x<=z)
		{
			int now = R[0];
			F(i, R, 0) if (cnt[now]>cnt[i]) now = i;
			F(i, D, now)
			{
				Remove(i); F(j, R, i) Remove(j);
				Dfs(x + 1,y+flag[row[i]],z);
				F(j, L, i) Resume(j); Resume(i);
			}
		}
	}
	//重複覆寫

}dlx;

int main()
{
	read(T);
	while (T--)
	{
		scanf("%d%d", &n,&m);
		dlx.reset(n,n);
		int sum=0;
		for (int i=1;i<=n;i++)
		{
			scanf("%d",&dlx.flag[i]);
			sum+=dlx.flag[i];
		}
		memset(f,1,sizeof(f));
		for (int i=1;i<=n;i++)
		{
			f[i][i]=0;
			if (i==n) break;
			scanf("%d%d%d",&x,&y,&z);
			f[x][y]=f[y][x]=z;
		}
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				for (int k=1;k<=n;k++)
					f[j][k]=min(f[j][k],f[j][i]+f[i][k]);
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				if (f[i][j]<=m) dlx.insert(i,j);
		dlx.num=-1;
		dlx.Dfs(0,0,sum);
		if (dlx.num>=0) dlx.num=sum-dlx.num;
		printf("Case #%d: %d\n",++tt,dlx.num);
	}
	return 0;
}