LA 3126 出租车
2024-08-24 03:53:37
题目链接: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 ;
}
最新文章
- 4、项目的培训 - PMO项目管理办公室
- 理解css margin
- Win10上使用SVN遇到的一些问题
- FPSCalc——简单FPS观测类
- robotframework笔记26
- 用java写bp神经网络(二)
- redis使用Java学习
- codeforces 659C Tanya and Toys
- hive内置函数大全
- Visual Studio 2017正式版离线安装及介绍
- Python函数篇:装饰器
- IntelliJ IDEA使用心得之基础篇
- .net 远程调试
- python︱Anaconda安装、简介(安装报错问题解决、Jupyter Notebook)
- JavaScript的数组实现队列与堆栈的方法
- request.getContextPath()
- Android四大组件之 --- Service入门
- (四)juc线程高级特性——线程池 / 线程调度 / ForkJoinPool
- C++STL queue
- OC调用Swift