链接:

http://acm.hdu.edu.cn/showproblem.php?pid=2389

不能用匈牙利,会TEL的,用Hopcroft-Karp

Hopcroft-Karp课件

以前是寻找一个增广路,这个是寻找所有的增广路,并且使用BFS进行分层

代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std; #define N 3100
#define INF 0xfffffff struct node
{
int x, y, s;
} x[N], y[N]; struct Node
{
int v, next;
} a[N*N]; int head[N], cnt, n, m;
bool used[N];
int Mx[N], My[N], depth; ///记录的所匹配的端点,0表示未匹配
int dx[N], dy[N]; ///BFS分层时,记录点所在的层,-1表示不在分层 void Init()
{
cnt = ;
memset(head, -, sizeof(head));
} void Add(int u, int v)
{
a[cnt].v = v;
a[cnt].next = head[u];
head[u] = cnt++;
} bool BFS()///如果发现y这边有增广路,返回1,否则返回0
{
queue<int> Q; depth = INF; memset(dx, -, sizeof(dx));
memset(dy, -, sizeof(dy)); for(int i=; i<=n; i++)
{
if( Mx[i] == false )
{
dx[i] = ;
Q.push(i);
}
} while(Q.size())
{
int u = Q.front(); Q.pop();
if(dx[u] > depth) break;///已经找到了增广路,不必寻找下层 for(int j=head[u]; j!=-; j=a[j].next)
{
int v = a[j].v; if( dy[v] == - )
{
dy[v] = dx[u] + ; if(My[v] == false)
depth = dy[v];
else
{
dx[ My[v] ] = dy[v] + ;
Q.push( My[v] );
}
}
}
} if( depth == INF )
return false;
return true;
}
bool Find(int i)
{
for(int j=head[i]; j!=-; j=a[j].next)
{
int v = a[j].v; if( !used[v] && dx[i] == dy[v]-)
{
used[v] = true; if( My[v] && dy[v] == depth )
continue;///不会在下一层,因为还没有对下层进行增广 if( !My[v] || Find( My[v] ) )
{
My[v] = i;
Mx[i] = v;
return true;
}
}
} return false;
} int Karp()
{
int ans = ;
memset(Mx, false, sizeof(Mx));
memset(My, false, sizeof(My)); while( BFS() == true )
{///如果还存在增广路
memset(used, false, sizeof(used));
for(int i=; i<=n; i++)
{
if( !Mx[i] && Find(i) == true )
ans++;
}
} return ans;
} int main()
{
int t, iCase=; scanf("%d", &t);
while(t--)
{
int time, i, j; scanf("%d%d", &time, &n);
Init();
for(i=; i<=n; i++)
{
scanf("%d%d%d", &x[i].x, &x[i].y, &x[i].s);
x[i].s = x[i].s*x[i].s*time*time;
} scanf("%d", &m);
for(i=; i<=m; i++)
{
scanf("%d%d", &y[i].x, &y[i].y);
for(j=; j<=n; j++)
{
int d = (y[i].x-x[j].x)*(y[i].x-x[j].x) + (y[i].y-x[j].y)*(y[i].y-x[j].y);
if( d <= x[j].s )
Add(j, i);
}
} int ans = Karp(); printf("Scenario #%d:\n%d\n\n", iCase++, ans);
}
return ;
}

最新文章

  1. URL请求工具
  2. Hex string convert to Binary String and Vise-Versa(16进制和2进制字符串的相互转换)
  3. Sql中的Merge和output
  4. 深入HTML5 Web Worker应用实践:多线程编程
  5. maven install 时提示“程序包 javax.crypto不存在”
  6. 转:SSDB:快速取代redis的nosql
  7. (DP)House Robber
  8. HDU3790-最短路径问题
  9. 《android开发艺术探索》读书笔记(十四)--JNI和NDK编程
  10. 数据可视化——阿里云解决方案DataV
  11. L2-018 多项式A除以B(模拟)
  12. 20175316 盛茂淞 2018-2019-2 《Java程序设计》实验二 面向对象程序设计 实验报告
  13. gitlab数据库
  14. 远程服务调用RPC框架介绍,微服务架构介绍和RPC框架对比,dubbo、SpringClound对比
  15. MYSQL 总结——1
  16. [UE4]Get All Widgets Of Class、Get All Widgets with Interface,根据类名或者接口UI实例对象
  17. Linux和Windows中查看端口占用情况
  18. Antlr4 SQL Query 解析实例
  19. 报错:Cannot create PoolableConnectionFactory (The server time zone value &#39;CST&#39; is unrecognized or represents more than one time zone. You must configure either the server or JDBC driver (via the serverT
  20. Apply Bug10010310 On Oracle RAC 10.2.0.5

热门文章

  1. NHibernate ConfORM Mapping
  2. jdbc练习demo
  3. 操作表单域中的value值
  4. Hyberledger-Fabric 1.00 RPC学习(2)尝试建立一个network
  5. C++指针的长度
  6. vim删除行首数字
  7. 「小程序JAVA实战」小程序的分享和下载功能(69)
  8. MySQL函数及用法示例
  9. Git---远程仓库之从远程仓库克隆03
  10. window.addEventListener()/window.postMessage(”text“, &#39;*&#39;)