2015
09-17

# Little Wish~ lyrical step~

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?

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 ith number means the ith 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 ath node and bth node, and the length of the edge is w (1 <= w <= 10000000).

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 ith number means the ith 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 ath node and bth node, and the length of the edge is w (1 <= w <= 10000000).

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

Case #1: 1

1）求得并不是最小的重复覆盖，而是在一定数目条件下，交换人数最少的次数，因此，要搜遍整棵树（也就是搜完所有可能），而不能使用迭代Ａ*的方法。

2）如果完全搜整棵树会TLE，因此要加入一些剪枝，剪枝为，如果当前需要交换的节点数大于限制，则直接return.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inf 0x3f3f3f
using namespace std;
const int maxn=60;
const int maxr=maxn*maxn+maxn;
int n,D;
int child[maxn];
int boys;
bool flag;
int map[maxn][maxn];
void init_m()//初始化图
{
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
{
if(i==j)
{
map[i][j]=0;
}
else
{
map[i][j]=inf;
}
}
}
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(map[i][k]+map[k][j]<map[i][j])
{
map[i][j]=map[i][k]+map[k][j];
}
}
}
struct node
{
int l,r;
int u,d;
int s,c;
};
node dlx[maxr];
int h[maxn];
int limit;
int Q[maxn];
int X[maxr];
int hash[maxn];
void init(int r,int c)
{
for(int i=0; i<=c; i++)
{
dlx[i].s=0;
dlx[i].u=dlx[i].d=i;
dlx[i].r=i+1;
dlx[i+1].l=i;
}
size=c;
dlx[c].r=0;
while(r)
{
h[r--]=-1;
}
}
{
int tmp=++size;
dlx[c].s++;
dlx[tmp].c=c;
X[tmp]=r;
dlx[tmp].d=dlx[c].d;
dlx[tmp].u=c;
dlx[dlx[c].d].u=tmp;
dlx[c].d=tmp;
if(h[r]<0)
{
h[r]=dlx[tmp].l=dlx[tmp].r=tmp;
}
else
{
dlx[tmp].r=dlx[h[r]].r;
dlx[tmp].l=h[r];
dlx[dlx[h[r]].r].l=tmp;
dlx[h[r]].r=tmp;
}
}
void remove(int x)
{
for(int i=dlx[x].d; i!=x; i=dlx[i].d)
{
dlx[dlx[i].r].l=dlx[i].l;
dlx[dlx[i].l].r=dlx[i].r;
dlx[dlx[i].c].s--;
}
}
void resume(int x)
{
for(int i=dlx[x].u; i!=x; i=dlx[i].u)
{
dlx[dlx[i].r].l=i;
dlx[dlx[i].l].r=i;
dlx[dlx[i].c].s++;
}
}
int hh()
{
int ret=0;
memset(hash,0,sizeof(hash));
{
if(hash[i]==false)
{
hash[i]=true;
ret++;
for(int j=dlx[i].d; j!=i; j=dlx[j].d)
for(int k=dlx[j].r; k!=j; k=dlx[k].r)
{
hash[dlx[k].c]=true;
}
}
}
return ret;
}
void dlx_dfs(int k)
{
if(k+hh()>boys)//最大的限制为男生总数
{
return;
}
int ssd=0;
for(int i=0;i<k;i++)
{
ssd+=child[Q[i]];
}
if(k-ssd>=limit) return;//剪枝判断
{
flag=true;
limit=k-ssd;
return;
}
int minn=n+2;
int tt;
{
if(minn>dlx[i].s)
{
minn=dlx[i].s;
tt=i;
}
}
for(int i=dlx[tt].d; i!=tt; i=dlx[i].d)
{
Q[k]=X[i];
remove(i);
for(int j=dlx[i].r; j!=i; j=dlx[j].r)
{
remove(j);
}
dlx_dfs(k+1);
for(int j=dlx[i].l; j!=i; j=dlx[j].l)
{
resume(j);
}
resume(i);
}
return;
}
int main()
{
// freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
int cas=1;
while(t--)
{
printf("Case #%d: ",cas++);
scanf("%d%d",&n,&D);
boys=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&child[i]);
if(child[i]==1)
{
boys++;
}
}
init_m();
int a,b,c;
for(int i=0;i<n-1;i++)//正反建图
{
scanf("%d%d%d",&a,&b,&c);
map[a][b]=c;
map[b][a]=c;
}
floyd();
init(n,n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(map[i][j]<=D)
{
}
}
flag=false;
limit=inf;
dlx_dfs(0);
if(!flag)
{
printf("-1\n");
}
else
{
printf("%d\n",limit);
}
}
return 0;
}