題意：

公園管理層最終決定在公園的各個戰(zhàn)略位置安裝一些流行的拳擊機(jī)。實(shí)際上，為了彌補(bǔ)以前缺少的機(jī)器，他們決定安裝盡可能多的機(jī)器。令人驚訝的是，公園不會被新機(jī)器堵塞，因?yàn)閷τ跈C(jī)器的位置存在一些非常嚴(yán)重的法律限制。管理層已經(jīng)標(biāo)記了所有可能的拳擊機(jī)位置以及它們在公園計(jì)劃中的相應(yīng)坐標(biāo)。此外，他們還必須遵守制造商安全規(guī)則：任何兩臺拳擊機(jī)之間的距離必須至少為1.3米。幫助管理層確定可安裝在公園內(nèi)的最大數(shù)量的裝箱機(jī)。

分析：二分圖匹配。給距離小于1.3的兩個點(diǎn)建邊，之后求最大匹配，每有一個匹配就說明有兩個點(diǎn)相鄰，所以答案是 n - 最大匹配數(shù)

代碼：

#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <vector> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define ll long long #define mod 1000000007 #define lowbit(x) (x&(-x)) #define mem(a) memset(a,0,sizeof(a)) #define FRER() freopen("in.txt","r",stdin); #define FREW() freopen("out.txt","w",stdout);using namespace std;typedef pair<int,int> pii; const int maxn = 2000 + 7 , inf = 0x3f3f3f3f ; struct Node{int x,y; }nodes[maxn]; int nxt[maxn*100],to[maxn*100],head[maxn*100];//數(shù)組開大會TLE int vis[maxn],used[maxn]; int n,nEdge;void add(int u,int v){nxt[nEdge] = head[u];to[nEdge] = v;head[u] = nEdge++; } void read(){nEdge = 0;memset(head,-1,sizeof(head));mem(vis);mem(used);mem(nxt);mem(to);mem(nodes);for(int i=1;i<=n;i++)scanf("%d %d",&nodes[i].x,&nodes[i].y); } bool can(Node a,Node b){double x1 = 1.0*a.x;double y1 = 1.0*a.y;double x2 = 1.0*b.x;double y2 = 1.0*b.y;double res = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));if(res<=1.3) return true;return false; }bool dfs(int u){for(int i = head[u];~i;i=nxt[i]){int v = to[i];if(!vis[v]){vis[v] = 1;if(!used[v]||dfs(used[v])){used[v] = u;used[u] = v;return true;}}}return false; }int Hungary(){int res = 0;for(int i=1;i<=n;i++){mem(vis);if(!used[i]&&dfs(i)) res++;//這個地方要判斷這個點(diǎn)是否被匹配了}return res; }int main(){//FRER();while(~scanf("%d",&n)){read();for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(can(nodes[i],nodes[j])){add(i,j);add(j,i);}}}int ans = Hungary();printf("%d\n",n - ans);}}

?

轉(zhuǎn)載于:https://www.cnblogs.com/seven7777777/p/10278703.html

總結(jié)

以上是生活随笔為你收集整理的CTU 2017 J - Punching Power （二分图匹配）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。