hdu2295-Radar

有n个城市，\(m\)个雷达，\(k\)个操作员，每个操作员只能操作一个雷达。每个雷达的覆盖范围是一个以雷达坐标为中心的圆，所有雷达的覆盖半径是相同的。

现在给出这\(n\)个城市，\(m\)个雷达的坐标，问雷达覆盖半径最小是多少，让所有城市都可以被雷达覆盖到。

\(T\le 1000,n,m,k\le 50,x,y\le 1000\)。

分析

二分答案，转化成判定性问题。这是一个最小支配集问题，已经被证明是NP难的，没有多项式的解法，所以使用搜索。又注意到这是一个覆盖的问题，可以使用Dancing Links数据结构来优化搜索。

这与DLX的一般问题，精确覆盖问题是不同的，因为一个城市可以被多个雷达覆盖，所以这是一个重复覆盖问题。这同样可以用DLX解决，因为它只是一个加速删除和回溯的数据结构而已。

重复覆盖，就是说一个列可以被覆盖多次，但每一列都要被覆盖。这样的话，我们只要每次在删除和回溯的时候，都只删除当前选择的这一行的所有元素的那些列，而不继续删除那些节点所在的行。这个在实现上有一些技巧。



for (int i=p[first].d;i!=first;i=p[i].d) {

	del(i);

	for (int j=p[i].r;j!=i;j=p[j].r) del(j);

	bool ret=dance(now+1);

	if (ret) return ret;

	for (int j=p[i].l;j!=i;j=p[j].l) back(j);

	back(i);

}

我们删除一列不是从列标开始删除，而是从当前的节点循环删除一轮，并且不删除当前节点。这是为了方便继续往下遍历，而且不删当前节点是没有影响的，因为这列上除了当前节点的点都被删掉了，所以不会访问到。而从行访问也是不需要的，所以可以这样做。

然而这样会TLE，因为在重复覆盖问题中，节点个数减少得很慢，导致算法的效率降低。所以我们一般需要加一些剪枝（其实一般都要加的），例如这题中的估价剪枝。

如果当前的答案加上最少需要再选多少行才能覆盖（只能估少，不能估多），已经大于\(k\)了，那么就可以剪掉。这个估价的方法是，枚举当前存在的每一列，如果没有tic就便利这一列有关的所有行，把所有行有关的列都打上tic，这算作选了一次，因为选的次数至少是这么多。

代码

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const double eps=1e-8;

const int maxn=55;

const int maxm=maxn*maxn;

struct cord {

	double x,y;

} city[maxn],radar[maxn];

double dist(cord &a,cord &b) {

	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

int n,m,k;

struct node {

	int l,r,u,d,col,row;

};

struct DLX {

	node p[maxm];

	int tot,last[maxn],size[maxn];

	bool tic[maxn];

	void clear() {

		memset(p,0,sizeof p);

		memset(last,0,sizeof last),memset(size,0,sizeof size);

		tot=n;

		p[0]=(node){n,1,0,0,0,0};

		for (int i=1;i<=n;++i) {

			p[i]=(node){i-1,i+1,i,i,0,i};

			last[i]=i;

		}

		p[n].r=0;

	}

	void build(int row,int a[],int len) {

		if (!len) return;

		p[++tot]=(node){tot,tot,last[a[1]],p[last[a[1]]].d,a[1],row};

		p[p[tot].u].d=p[p[tot].d].u=last[a[1]]=tot;

		++size[a[1]];

		for (int i=2;i<=len;++i) {

			int x=a[i];

			p[++tot]=(node){tot-1,p[tot-1].r,last[x],p[last[x]].d,x,row};

			p[p[tot].l].r=p[p[tot].r].l=p[p[tot].u].d=p[p[tot].d].u=last[x]=tot;

			++size[x];

		}

	}

	void del(int c) {

		for (int i=p[c].d;i!=c;i=p[i].d) p[p[i].l].r=p[i].r,p[p[i].r].l=p[i].l,--size[p[i].col];

	}

	void back(int c) {

		for (int i=p[c].u;i!=c;i=p[i].u) p[p[i].l].r=p[p[i].r].l=i,++size[p[i].col];

	}

	int mi() {

		memset(tic,0,sizeof tic);

		int ret=0;

		for (int i=p[0].r;i;i=p[i].r) if (!tic[i]) {

			++ret;

			tic[i]=true;

			for (int j=p[i].d;j!=i;j=p[j].d) for (int q=p[j].r;q!=j;q=p[q].r) tic[p[q].col]=true;

		}

		return ret;

	}

	bool dance(int now) {

		if (!p[0].r) return now<=k;

		if (now+mi()>k) return false;

		int first=p[0].r;

		for (int i=p[0].r;i;i=p[i].r) if (size[i]<size[first]) first=i;

		for (int i=p[first].d;i!=first;i=p[i].d) {

			del(i);

			for (int j=p[i].r;j!=i;j=p[j].r) del(j);

			bool ret=dance(now+1);

			if (ret) return ret;

			for (int j=p[i].l;j!=i;j=p[j].l) back(j);

			back(i);

		}

		return false;

	}

} dlx;

bool ok(double rad) {

	dlx.clear();

	for (int i=1;i<=m;++i) {

		static int c[maxn];

		int tot=0;

		for (int j=1;j<=n;++j)

			if (dist(radar[i],city[j])<=rad)

				c[++tot]=j;

		dlx.build(i,c,tot);

	}

	bool flag=dlx.dance(0);

	return flag;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

#endif

	int T;

	scanf("%d",&T);

	while (T--) {

		scanf("%d%d%d",&n,&m,&k);

		for (int i=1;i<=n;++i) scanf("%lf%lf",&city[i].x,&city[i].y);

		for (int i=1;i<=m;++i) scanf("%lf%lf",&radar[i].x,&radar[i].y);

		double l=0,r=2000,ans,mid;

		while (fabs(l-r)>eps) {

			mid=(l+r)/2;

			if (ok(mid)) ans=mid,r=mid; else l=mid;

		}

		printf("%.6lf\n",ans);

	}

	return 0;

}

巴特西

hdu2295-Radar

分析

代码

最新文章

热门文章