題目鏈接

https://codeforces.com/gym/101221/

題解

又是一道看了題解的作業題。
這是一個最大團(或者補圖上的最大獨立集)問題，而二分圖最大獨立集是可以做的，因此可以考慮轉化成二分圖。
枚舉點集的直徑的兩端點 \(x,y\)，滿足 \(dis(x,y)\le d\)，那么剩下點的可選范圍就是兩個分別以 \(x,y\) 為圓心、\(dis(x,y)\) 為半徑的圓的交。

可以發現，以兩點連線為界，交的區域被分成了兩部分。如果兩個點距離大于 \(dis(x,y)\)，那么它們一定位于不同的兩部分。
于是天然的二分圖就構建好了！在上面求最大獨立集也就是用總點數減去最大匹配即可。
時間復雜度 \(O(n^{4.5})\)，但是跑得飛快，cf 上只用 \(46\text{ms}\).
另外 lk 的博客上說是 \(O(n^4)\)，但并不知道為什么。

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define x first #define y second #define iter iterator #define riter reverse_iterator #define y1 Lorem_ipsum_ #define tm dolor_sit_amet_ using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }namespace NetFlow {const int N = 202;const int M = 10200;const int INF = 1e6;struct Edge{int v,w,nxt;} e[(M<<1)+3];int fe[N+3];int te[N+3];int dep[N+3];int que[N+3];int n,en,s,t;void clear(){for(int i=1; i<=n; i++) fe[i] = te[i] = dep[i] = que[i] = 0;for(int i=1; i<=en; i++) e[i].v = e[i].w = e[i].nxt = 0;n = s = t = 0; en = 1;}void addedge(int u,int v,int w){ // printf("addedge %d %d %d\n",u,v,w);en++; e[en].v = v; e[en].w = w;e[en].nxt = fe[u]; fe[u] = en;en++; e[en].v = u; e[en].w = 0;e[en].nxt = fe[v]; fe[v] = en;}bool bfs(){for(int i=1; i<=n; i++) dep[i] = 0;int head = 1,tail = 1; que[1] = s; dep[s] = 1;while(head<=tail){int u = que[head]; head++;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(e[i].w>0 && dep[v]==0){dep[v] = dep[u]+1;if(v==t) return true;tail++; que[tail] = v;}}}return false;}int dfs(int u,int cur){if(u==t||cur==0) {return cur;}int rst = cur;for(int &i=te[u]; i; i=e[i].nxt){int v = e[i].v;if(e[i].w>0 && rst>0 && dep[v]==dep[u]+1){int flow = dfs(v,min(rst,e[i].w));if(flow>0){e[i].w -= flow; rst -= flow;e[i^1].w += flow;if(rst==0) {return cur;}}}}if(rst==cur) {dep[u] = -2;}return cur-rst;}int dinic(int _n,int _s,int _t){n = _n,s = _s,t = _t;int ret = 0;while(bfs()){for(int i=1; i<=n; i++) te[i] = fe[i];memcpy(te,fe,sizeof(int)*(n+1));ret += dfs(s,INF);}return ret;}void dfs2(int u){dep[u] = 1;for(int i=fe[u]; i; i=e[i].nxt) if(e[i].w>0){int v = e[i].v; if(dep[v]) continue;dfs2(v);}}void calcway(){for(int i=1; i<=n; i++) dep[i] = 0;dfs2(1);} } using NetFlow::addedge; using NetFlow::dinic;const int mxN = 100; struct Point {int x,y;}; typedef Point Vector; Point operator +(Point x,Point y) {return (Point){x.x+y.x,x.y+y.y};} Point operator -(Point x,Point y) {return (Point){x.x-y.x,x.y-y.y};} int Norm2(Vector x) {return x.x*x.x+x.y*x.y;} int Cross(Vector x,Vector y) {return x.x*y.y-x.y*y.x;}Point a[mxN+3]; vector<int> way; int n; int d;int main() {n = read(),d = read();for(int i=1; i<=n; i++) {a[i].x = read(),a[i].y = read();}int ans = 1; way.push_back(1);for(int x=1; x<=n; x++) for(int y=x+1; y<=n; y++) if(Norm2(a[x]-a[y])<=d*d){vector<int> s1,s2; int cd = Norm2(a[x]-a[y]);for(int i=1; i<=n; i++) if(i!=x&&i!=y&&Norm2(a[i]-a[x])<=cd&&Norm2(a[i]-a[y])<=cd){if(Cross(a[y]-a[x],a[i]-a[x])>=0) {s1.push_back(i);} else {s2.push_back(i);}}NetFlow::clear();for(int i=0; i<s1.size(); i++) addedge(1,i+3,1);for(int i=0; i<s2.size(); i++) addedge(i+s1.size()+3,2,1);for(int i=0; i<s1.size(); i++) for(int j=0; j<s2.size(); j++){if(Norm2(a[s2[j]]-a[s1[i]])>cd) {addedge(i+3,j+s1.size()+3,1);}}int cur = s1.size()+s2.size()-dinic(s1.size()+s2.size()+2,1,2)+2;if(cur>ans){ans = cur; way.clear(); way.push_back(x),way.push_back(y);NetFlow::calcway();for(int i=0; i<s1.size(); i++) if(NetFlow::dep[i+3]) {way.push_back(s1[i]);}for(int i=0; i<s2.size(); i++) if(!NetFlow::dep[i+s1.size()+3]) {way.push_back(s2[i]);}}}printf("%d\n",ans);for(int i=0; i<way.size(); i++) printf("%d ",way[i]); puts("");return 0; }

總結

以上是生活随笔為你收集整理的Gym 101221I [WF2014]Sensor Network (二分图匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。