gym101221I Sensor Network 题解

First Post:

Last Update:

自己做出来的，好耶！虽然童年时以为这是不可做问题。

题意：给定平面上 个点，构造一张 个点的图 ， 中两点有连边当且仅当欧氏距离不超过给定值 ，求 的最大团。 。

首先团的限制是非常严的，我们考虑充分利用这个限制。可以先尝试枚举一个点，此时所有点一定在以其为圆心，半径为 的圆内，发现限制不够强，没啥用。故考虑枚举在团中的两个点 ，使得 。

此时团中剩下的点一定在两圆之交的部分，我们用直线 把这个部分分成两半，我们发现每一半中的距离肯定 。这个性质还是没什么用，只不过启发了我们要关注这个直线分出来的两个部分。为了获得更强的限制，我们不妨假设 就是团中距离最大的那一对点，那此时我们以 为圆心， 为半径作圆，将这两个圆的交用直线 分成两个部分。不难发现，属于同一个部分中的点的距离肯定 。然后考虑 的补图，此时两个点有边当且仅当距离大于 ，我们要找这张图的最大独立集。容易发现同一个部分中的点肯定是没有连边的，所以这张图其实是二分图，求二分图的最大独立集即可。

关于如何求二分图的最大独立集，可以阅读这篇文章：一种最长反链的构造方法

时间复杂度 。可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5;
int n,D;
struct Vec {
	int x,y;
	Vec(){}
	Vec(const int _x,const int _y):x(_x),y(_y){}
	Vec operator + (const Vec &rhs) const { return Vec(x + rhs.x,y + rhs.y);}
	Vec operator - (const Vec &rhs) const { return Vec(x - rhs.x,y - rhs.y);}
	int operator * (const Vec &rhs) const { return x * rhs.y - y * rhs.x;}
};
inline int Dot(const Vec &A) { return A.x * A.x + A.y * A.y;}
inline int Dis(const Vec &A,const Vec &B) { return Dot(A - B);}
inline bool InTriangle(const Vec &A,const Vec &B,const Vec &C,const Vec &p) {
	if((B - A) * (p - A) >= 0 && (C - B) * (p - B) >= 0 && (A - C) * (p - C) >= 0) return true;
	if((B - A) * (p - A) <= 0 && (C - B) * (p - B) <= 0 && (A - C) * (p - C) <= 0) return true;
	return false;
}
Vec p[N];
namespace Flow {
	const int M = 2e6 + 5;
	int fir[N],nxt[M],to[M],w[M],ect = 1;
	inline void addedge(int u1,int v1,int w1) {
		nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;w[ect] = w1;
	}
	inline void ins(int u1,int v1,int w1) { addedge(u1,v1,w1);addedge(v1,u1,0);}
	int dep[N],cur[N],tot;
	inline void Clr(int _n) {
		tot = _n;ect = 1;
		for(int i = 1;i <= tot;i++) fir[i] = 0;
	}
	inline bool bfs(int S,int T) {
		for(int i = 1;i <= tot;i++) dep[i] = 1e9,cur[i] = fir[i];
		queue<int> Q;Q.push(S);dep[S] = 0;
		while(!Q.empty()) {
			int x = Q.front();Q.pop();
			for(int i = fir[x],y;y = to[i],i;i = nxt[i])
				if(w[i] && dep[y] > dep[x] + 1)
					dep[y] = dep[x] + 1,Q.push(y); 
		}
		return dep[T] < 1e9;
	}
	int dfs(int u,int t,int limit) {
		if(u == t || !limit) return limit;
		int flow = 0,f;
		for(int i = cur[u],v;v = to[i],i;i = nxt[i]) {
			cur[u] = i;
			if((dep[v] == dep[u] + 1) && w[i] && (f = dfs(v,t,min(limit,w[i])))) {
				flow += f;
				limit -= f;
				w[i] -= f;
				w[i ^ 1] += f;
				if(!limit) break;
			}
		}
		return flow;
	}
	inline int dinic(int S,int T) {
		int res = 0;
		while(bfs(S,T)) res += dfs(S,T,2e9);
		return res;
	}
}

struct Graph {
	int n1,n2;bool e[N][N];
	int mth[N],ismth[N];
	int vx[N],vy[N];
	void dfs(int x) {
		vy[x] = true;
		for(int i = 1;i <= n1;i++)
			if(!vx[i] && e[i][x] && mth[i] && !vy[mth[i]])
				vx[i] = true,dfs(mth[i]);
	}
	inline vector<int> GetSet() {
		if(!n1 && !n2) return vector<int>();
		vector<int> res;
		if(n1 && !n2) {
			for(int i = 1;i <= n1;i++) res.push_back(i);return res;
		}
		if(!n1 && n2) {
			for(int i = 1;i <= n2;i++) res.push_back(i + n1);return res;
		}
		Flow::Clr(n1 + n2 + 2);
		int S = n1 + n2 + 1,T = n1 + n2 + 2;
		for(int i = 1;i <= n1;i++) vx[i] = mth[i] = 0;
		for(int i = 1;i <= n2;i++) vy[i] = ismth[i] = 0;
		for(int i = 1;i <= n1;i++) Flow::ins(S,i,1);
		for(int i = 1;i <= n2;i++) Flow::ins(i + n1,T,1);
		for(int i = 1;i <= n1;i++)
			for(int j = 1;j <= n2;j++)
				if(e[i][j]) Flow::ins(i,j + n1,1);
		Flow::dinic(S,T);
		for(int i = 1;i <= n1;i++)
			for(int e = Flow::fir[i],j;j = Flow::to[e],e;e = Flow::nxt[e])
				if(j > n1 && Flow::w[e] == 0) { mth[i] = j - n1;ismth[mth[i]] = true;break;}

		for(int i = 1;i <= n2;i++) if(!ismth[i]) dfs(i);
		for(int i = 1;i <= n1;i++) if(!vx[i]) res.push_back(i);
		for(int i = 1;i <= n2;i++) if(vy[i]) res.push_back(i + n1);
		for(int i = 1;i <= n1;i++)
			for(int j = 1;j <= n2;j++)
				if(!vx[i] && vy[j]) assert(!e[i][j]);
		return res;
	}
} G;
vector<int> Ans;
int main() {
	cin >> n >> D;D = D * D;
	for(int i = 1;i <= n;i++) cin >> p[i].x >> p[i].y;
	Ans.push_back(1);
	for(int a = 1;a <= n;a++)
		for(int b = a + 1;b <= n;b++) {
			if(Dis(p[a],p[b]) > D) continue;
			int dab = Dis(p[a],p[b]);
			vector<int> p1,p2;
			for(int i = 1;i <= n;i++)
				if(i != a && i != b && Dis(p[a],p[i]) <= dab && Dis(p[b],p[i]) <= dab) {
					if((p[i] - p[a]) * (p[b] - p[a]) >= 0) p1.push_back(i);
					else p2.push_back(i);
				}
			G.n1 = p1.size();G.n2 = p2.size();
			// printf("a,b,n1,n2:%d,%d,%d,%d\n",a,b,G.n1,G.n2);
			for(int i = 1;i <= G.n1;i++) for(int j = 1;j <= G.n2;j++) G.e[i][j] = 0;
			for(int i = 0;i < p1.size();i++)
				for(int j = 0;j < p2.size();j++)
					if(Dis(p[p1[i]],p[p2[j]]) > dab) G.e[i + 1][j + 1] = true;
			auto res = G.GetSet();
			for(auto &it : res) {
				if(it <= G.n1) it = p1[it - 1];
				else it = p2[it - G.n1 - 1];
			}
			res.push_back(a);res.push_back(b);
			if(res.size() > Ans.size()) Ans = res;
		}
	printf("%d\n",(int)Ans.size());
	for(int i = 0;i < Ans.size();i++) printf("%d%c",Ans[i],(i == (int)Ans.size() - 1) ? '\n' : ' ');
	return 0;
}
≡