HDU4735 – Little Wish~ lyrical step~（DLX）

【传送门】HDU4735

【题意】给出一颗N(<=50)结点的树，每个节点上分别站着一个男孩(1)或女孩(0)，每个男孩可以保护离她距离<=D的所有女孩，还可以交换结点，每次可以交换任意两个结点，求交换最小次数可以让每个女孩都收到至少一个男孩的保护。不存在输出-1。

【分析】和选择<=k个结点覆盖所有结点其实差不多的，这里的任意交换两个结点其实就是任意选择<=k(k是男孩的总数)个结点覆盖所有他能保护范围内的点，这样行列都是n，跑一边可重复DLX即可。

需要注意DLX的时候要多维护一个值，表示已经改变的数量，这个就是答案。

【AC CODE】1076ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,b) for(int i = b[a];i != a; i = b[i])
const int INF = 0x3f3f3f3f, MAXN = 50+10,M = MAXN*MAXN;
int head[MAXN],all,nxt[MAXN<<1],to[MAXN<<1],cost[MAXN<<1];
int k,d,a[MAXN];

void add_edge(int u, int v, int w)
{
	nxt[all] = head[u],to[all] = v;cost[all] = w;
	head[u] = all++;
}
int vis[MAXN],dis[MAXN];
void bfs(int st)
{
	queue<int> q;
	clc(vis,0);
	q.push(st);
	dis[st] = 0;
	vis[st] = 1;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = head[u]; ~i; i = nxt[i])
		{
			int v = to[i];
			if(vis[v]) continue;
			if(dis[u]+cost[i] <= d)
			{
				vis[v] = true;
				dis[v] = dis[u]+cost[i];
				q.push(v);
			}
		}
	}
}
int lt[M],rt[M],up[M],down[M],row[M],col[M],tol,cnt[MAXN];
void init(int maxc)
{
	repe(i,0,maxc) lt[i] = i-1,rt[i] = i+1,up[i] = down[i] = col[i] = i;
	lt[0] = maxc,rt[maxc] = 0;
	tol = maxc+1;
	clc(cnt,0);
}
void remove(int c)
{
	FOR(i,c,down) lt[rt[i]] = lt[i],rt[lt[i]] = rt[i],--cnt[col[i]];
}
void reset(int c)
{
	FOR(i,c,up) lt[rt[i]] = rt[lt[i]] = i,++cnt[col[i]];
}
int f()
{
	int ans = 0;
	FOR(c,0,rt) vis[c] = true;
	FOR(c,0,rt)
	{
		if(vis[c])
		{
			ans++;
			vis[c] = false;
			FOR(i,c,down)
			{
				FOR(j,i,rt)
					vis[col[j]] = false;
			}
		}
	}
	return ans;
}
int mi;
void dfs(int d, int sum)
{
	if(d+f() > k || sum >= mi) return;
	if(!rt[0])
	{
		mi = sum;
		return;
	}
	int c = rt[0];
	FOR(i,0,rt) if(cnt[i] < cnt[c]) c = i;
	FOR(i,c,down)
	{
		remove(i);
		FOR(j,i,rt) remove(j);
		dfs(d+1,sum+(!a[row[i]]));
		FOR(j,i,lt) reset(j);
		reset(i);
	}
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t,count = 0;
	scanf("%d", &t);
	while(t--)
	{
		int n;
		scanf("%d %d",&n, &d);
		k = 0;
		repe(i,1,n) scanf("%d", &a[i]), k += a[i];
		clc(head,-1);
		all = 0;
		rep(i,1,n)
		{
			int u,v,w;
			scanf("%d %d %d", &u, &v, &w);
			add_edge(u,v,w);
			add_edge(v,u,w);
		}
		init(n);
		repe(i,1,n)
		{
			int ft = tol;
			bfs(i);
			repe(j,1,n)
			{
				if(vis[j])
				{
					row[tol] = i,col[tol] = j;
					lt[tol] = tol-1,rt[tol] = tol+1,up[tol] = up[j],down[tol] = j;
					down[up[j]] = tol, up[j] = tol;
					cnt[j]++,tol++;
				}
			}
			lt[ft] = tol-1,rt[tol-1] = ft;
		}
		mi = INF;
		clc(vis,0);
		dfs(0,0);
		printf("Case #%d: ", ++count);
		if(INF == mi) puts("-1");
		else printf("%d\n",mi);
	}
	return 0;
}