题目链接:https://vjudge.net/problem/UVALive-3126

题意:有m个客人,位于不同的位置,去一些地方,出发的时间给出,要一些出租车去接,但是,每辆出租车要在出发前一分钟要到,问:最少要几辆出租车;

分析:最少路径覆盖(在图中找尽量少的路径,使得每个节点恰好在一条路径上)

建图: 一个点拆成 i i',i->j 就连一条边到 j';

答案是 n - 最大匹配;

证明:之前有证明过,很有意思;

这里,就是从一个接完客人到另下一个客人,是否可以接到,能就连一条边;

 #include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std; const int maxn = + ; // 单侧顶点的最大数目 struct BPM {
int n,m;
vector<int> G[maxn];
int left[maxn];
bool T[maxn]; int right[maxn];
bool S[maxn]; void init(int n,int m) {
this->n = n;
this->m = m;
for(int i=; i<n; i++)
G[i].clear();
} void AddEdge(int u,int v) {
G[u].push_back(v);
} bool match(int u) {
S[u] = true;
for(int i=; i<G[u].size(); i++) {
int v = G[u][i];
if(!T[v]) {
T[v] = true;
if(left[v]==-||match(left[v])) {
left[v] = u;
right[u] = v;
return true;
}
}
}
return false;
} int solve() {
memset(left,-,sizeof(left));
memset(right,-,sizeof(right));
int ans = ;
for(int u=; u<n; u++) {
memset(S,,sizeof(S));
memset(T,,sizeof(T));
if(match(u))
ans++;
}
return ans;
} } sol; int x1[maxn], y1[maxn], x2[maxn], y2[maxn], t1[maxn], t2[maxn]; int dist(int a, int b, int c, int d) {
return abs(a-c) + abs(b-d);
} int main() {
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
for(int i = ; i < n; i++) {
int h, m;
scanf("%d:%d%d%d%d%d", &h, &m, &x1[i], &y1[i], &x2[i], &y2[i]);
t1[i] = h*+m;
t2[i] = t1[i] + dist(x1[i], y1[i], x2[i], y2[i]);
}
sol.init(n, n);
for(int i = ; i < n; i++)
for(int j = i+; j < n; j++)
if(t2[i] + dist(x2[i], y2[i], x1[j], y1[j]) < t1[j])
sol.AddEdge(i,j);
printf("%d\n", n - sol.solve());
}
return ;
}

最新文章

  1. 4、项目的培训 - PMO项目管理办公室
  2. 理解css margin
  3. Win10上使用SVN遇到的一些问题
  4. FPSCalc——简单FPS观测类
  5. robotframework笔记26
  6. 用java写bp神经网络(二)
  7. redis使用Java学习
  8. codeforces 659C Tanya and Toys
  9. hive内置函数大全
  10. Visual Studio 2017正式版离线安装及介绍
  11. Python函数篇:装饰器
  12. IntelliJ IDEA使用心得之基础篇
  13. .net 远程调试
  14. python︱Anaconda安装、简介(安装报错问题解决、Jupyter Notebook)
  15. JavaScript的数组实现队列与堆栈的方法
  16. request.getContextPath()
  17. Android四大组件之 --- Service入门
  18. (四)juc线程高级特性——线程池 / 线程调度 / ForkJoinPool
  19. C++STL queue
  20. OC调用Swift

热门文章

  1. linux中终端字体样式显示不正常
  2. C++ 调用Python3
  3. python3 模块安装列表
  4. spark第六篇:Spark Streaming Programming Guide
  5. ibaits数组形式批量入库
  6. web安全漏洞种类
  7. Xlua文件在热更新中调用方法
  8. linux安装PHP加速器eAccelerator
  9. Jersey统一异常处理
  10. python 将excel转换成字典,并且将字典写到txt文件里