首页 > 代码库 > LA 3126 出租车
LA 3126 出租车
题目链接：https://vjudge.net/problem/UVALive-3126
题意：有m个客人，位于不同的位置，去一些地方，出发的时间给出，要一些出租车去接，但是，每辆出租车要在出发前一分钟要到，问：最少要几辆出租车；
分析：最少路径覆盖（在图中找尽量少的路径，使得每个节点恰好在一条路径上）
建图： 一个点拆成 i i‘，i->j 就连一条边到 j‘；
答案是 n - 最大匹配；
证明：之前有证明过，很有意思；
这里，就是从一个接完客人到另下一个客人，是否可以接到，能就连一条边；
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 500 + 5; // 单侧顶点的最大数目 8 9 struct BPM {10 int n,m;11 vector<int> G[maxn];12 int left[maxn];13 bool T[maxn];14 15 int right[maxn];16 bool S[maxn];17 18 void init(int n,int m) {19 this->n = n;20 this->m = m;21 for(int i=0; i<n; i++)22 G[i].clear();23 }24 25 void AddEdge(int u,int v) {26 G[u].push_back(v);27 }28 29 bool match(int u) {30 S[u] = true;31 for(int i=0; i<G[u].size(); i++) {32 int v = G[u][i];33 if(!T[v]) {34 T[v] = true;35 if(left[v]==-1||match(left[v])) {36 left[v] = u;37 right[u] = v;38 return true;39 }40 }41 }42 return false;43 }44 45 int solve() {46 memset(left,-1,sizeof(left));47 memset(right,-1,sizeof(right));48 int ans = 0;49 for(int u=0; u<n; u++) {50 memset(S,0,sizeof(S));51 memset(T,0,sizeof(T));52 if(match(u))53 ans++;54 }55 return ans;56 }57 58 } sol;59 60 61 int x1[maxn], y1[maxn], x2[maxn], y2[maxn], t1[maxn], t2[maxn];62 63 int dist(int a, int b, int c, int d) {64 return abs(a-c) + abs(b-d);65 }66 67 int main() {68 int T;69 scanf("%d", &T);70 while(T--) {71 int n;72 scanf("%d", &n);73 for(int i = 0; i < n; i++) {74 int h, m;75 scanf("%d:%d%d%d%d%d", &h, &m, &x1[i], &y1[i], &x2[i], &y2[i]);76 t1[i] = h*60+m;77 t2[i] = t1[i] + dist(x1[i], y1[i], x2[i], y2[i]);78 }79 sol.init(n, n);80 for(int i = 0; i < n; i++)81 for(int j = i+1; j < n; j++)82 if(t2[i] + dist(x2[i], y2[i], x1[j], y1[j]) < t1[j])83 sol.AddEdge(i,j);84 printf("%d\n", n - sol.solve());85 }86 return 0;87 }
LA 3126 出租车
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。