POJ 2536 Gopher II(二分图最大匹配)
http://poj.org/problem?id=2536
题意:
有n个地鼠和m个洞,有鹰飞来时,n个地鼠如果能在s秒从当前位置回到一个洞,就能不死,一个洞能容纳一个地鼠,它们的速度为v。求可能死的地鼠个数的最小值。
分析:
如果一个地鼠能在s秒内到达一个特定的洞,那么就在它们之间两一条无向边. 我们所建立的图是一个二分图,左边是地鼠,右边是洞.
现在我们要求的就是该图的最大匹配数.
那么可能死的地鼠个数 = n – 最大匹配数.
AC代码:
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=100+5;
struct Max_Match
{
int n,m;
bool g[maxn][maxn];
bool vis[maxn];
int left[maxn];
void init(int n,int m)
{
this->n=n;
this->m=m;
memset(g,0,sizeof(g));
memset(left,-1,sizeof(left));
}
bool match(int u)
{
for(int v=1;v<=m;v++)if(g[u][v] && !vis[v])
{
vis[v]=true;
if(left[v]==-1 || match(left[v]))
{
left[v]=u;
return true;
}
}
return false;
}
int solve()
{
int ans=0;
for(int i=1;i<=m;i++)
{
memset(vis,0,sizeof(vis));
if(match(i)) ans++;
}
return ans;
}
}MM;
struct Point
{
double x,y;
void read()
{
scanf("%lf%lf",&x,&y);
}
}P1[maxn],P2[maxn];
double get_dist(int i,int j)
{
return sqrt( (P1[i].x-P2[j].x)*(P1[i].x-P2[j].x)+(P1[i].y-P2[j].y)*(P1[i].y-P2[j].y) );
}
int main()
{
int n,m,s,v;
while(scanf("%d%d%d%d",&n,&m,&s,&v)==4)
{
MM.init(n,m);
for(int i=1;i<=n;i++)
P1[i].read();
for(int i=1;i<=m;i++)
P2[i].read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(get_dist(i,j) <= s*v )
{
MM.g[i][j]=true;
}
}
printf("%d\n",n-MM.solve());
}
return 0;
}
分享到:
相关推荐
4. POJ2536: 地鼠和地鼠洞的问题可以通过构建二分图来解决。地鼠和地鼠洞是二分图的两个集合,如果一只地鼠能在老鹰到达前跑到某个洞,就在它们之间建立边。求解最小的被吃地鼠数,即求二分图的最大匹配。 5. POJ...
* 二分图的最大匹配:二分图的最大匹配是指计算二分图的最大匹配的算法,如 poj3041、poj3020。 * 最大流的增广路算法:最大流的增广路算法是指计算图的最大流的算法,如 poj1459、poj3436。 三、数据结构 数据...
poj openjudge 1111题最大正向匹配 提交ac
* 二分图的最大匹配:例如 poj3041、poj3020。 * 最大流的增广路算法:例如 poj1459、poj3436。 3. 数据结构: * 串:例如 poj1035、poj3080、poj1936。 * 排序:例如 poj2388、poj2299。 * 简单并查集的应用...
- **二分图最大匹配**:匈牙利算法,如poj3041和poj3020,解决分配问题。 - **最大流的增广路算法**:KM算法,如poj1459和poj3436,用于寻找网络中能传输的最大流量。 3. **数据结构**: - **字符串处理**:如...
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) ... (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ3007-Organize Your Train part II 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
2. **图算法**:包括图的深度优先遍历、广度优先遍历、最短路径算法、最小生成树算法、拓扑排序、二分图的最大匹配以及最大流的增广路算法。如poj3278、poj2049、poj3083是图遍历的例子,poj1860、poj3259等则是最短...
* 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * 最大流的增广路算法:KM算法 + poj1459, poj3436 三、数据结构 * 串:poj1035, poj3080, poj1936 * 排序:快排、归并排、堆排 + poj2388, poj2299 * 简单...
* 二分图的最大匹配:二分图的最大匹配是指在二分图中寻找最大匹配的算法。例题:poj3041、poj3020。 * 最大流的增广路算法:最大流的增广路算法是指在流量网络中寻找最大流的算法。例题:poj1459、poj3436。 三、...
poj2516代码最小费用最大流
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
本部分涵盖了图算法,包括图的深度优先遍历和广度优先遍历、最短路径算法、最小生成树算法、拓扑排序、二分图的最大匹配和最大流的增广路算法。 (1) 图的深度优先遍历和广度优先遍历: (2) 最短路径算法:dijkstra,...
北大POJ初级-图算法 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
- 二分图的最大匹配:匈牙利算法,如POJ3041。 - 最大流:KM算法,如POJ1459。 3. **数据结构** - 串:处理字符串问题,如POJ1035。 - 排序:快速排序、归并排序和堆排序,如POJ2299。 - 并查集:处理不相交...
21. POJ——2719 陶陶摘苹果:这可能是一个贪心算法或动态规划问题,解决如何在有限时间内最大化苹果收获。 22. POJ——2720 大象喝水:可能涉及到体积计算和时间规划,解决大象喝水的最佳策略。 23. POJ——2722 ...