layout: post
title: 训练指南 UVALive - 3126(DAG 最小路径覆盖)
- author: "luowentaoaa"
- catalog: true
- mathjax: true
- tags:
- 二分图
- 图论
- 训练指南
- 最小路径覆盖
- Taxi Cab Scheme
- UVALive - 3126 https://vjudge.net/problem/32568/origin
题目大意: n 个客人, 从城市的不同位置出发, 到达他们的目的地. 已知每个人的出发时间 hh:mm, 出发地点 (x1,y1) 及目的地 (x2,y2), 要求使用最少的出租车接送乘客, 使得每个顾客的要求都被执行, 且每次出租车接客时需要至少提前一分钟到达乘客所在的位置. 城区是网格型的, 地址用(x,y) 表示, 出租车从 (x1,y1) 到(x2,y2)需要行驶 | x1 - x2| + |y1 - y2 | 分钟.
题目分析: 本题的模型是 DAG 上的最小路径覆盖. 将每个客人视为一个节点, 如果接送完顾客 i 后还可以继续接送顾客 j, 则对应 DAG 中的一条边 i -> j. 对每个节点拆点为 i,i', 如果图中存在有向边 i -> j, 则建边(i,j'). 设二分图的最大匹配数为 m, 则结果即为 n - m
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll mod=998244353;
- const int maxn=1e3+50;
- const ll inf=1e10;
- const ll INF = 1000000000;
- const double eps=1e-5;
- #define bug cout<<"bbibibibbbb="<<endl;
- /// 二分图最大基数匹配
- struct BPM{
- int n,m; /// 左右顶点个数
- int G[maxn][maxn]; /// 邻接表
- int left[maxn]; /// left[i]为右边第 i 个点的匹配点编号,-1 表示不存在
- bool T[maxn]; /// T[i]为右边第 i 个点是否已标记
- int right[maxn]; /// 求最小覆盖用
- bool S[maxn]; /// 求最小覆盖用
- void init(int n,int m){
- this->n=n;
- this->m=m;
- memset(G,0,sizeof(G));
- }
- /* void AddEdge(int u,int v){
- G[u].push_back(v);
- }*/
- bool match(int u){
- S[u]=true;
- for(int v=0;v<m;v++){
- //int v=G[u][i];
- if(G[u][v]&&!T[v]){
- T[v]=true;
- if(left[v]==-1||match(left[v])){
- left[v]=u;
- right[u]=v;
- return true;
- }
- }
- }
- return false;
- }
- /// 求最大匹配
- int solve(){
- memset(left,-1,sizeof(left));
- memset(right,-1,sizeof(right));
- int ans=0;
- for(int u=0;u<n;u++){
- memset(S,0,sizeof(S));
- memset(T,0,sizeof(T));
- if(match(u))ans++;
- }
- return ans;
- }
- /// 求最小覆盖. X 和 Y 为最小覆盖中的点集
- int mincover(vector<int>& X,vector<int>& Y){
- int ans=solve();
- memset(S,0,sizeof(S));
- memset(T,0,sizeof(T));
- for(int u=0;u<n;u++)
- if(right[u]==-1)match(u);
- for(int u=0;u<n;u++)
- if(!S[u])X.push_back(u);
- for(int v=0;v<n;v++)
- if(T[v])Y.push_back(v);
- return ans;
- }
- };
- BPM solver;
- int x1[maxn],yyy[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 = 0; i < n; i++) {
- int h, m;
- scanf("%d:%d%d%d%d%d", &h, &m, &x1[i], &yyy[i], &x2[i], &y2[i]);
- t1[i] = h*60+m;
- t2[i] = t1[i] + dist(x1[i], yyy[i], x2[i], y2[i]);
- }
- solver.init(n, n);
- for(int i = 0; i < n; i++)
- for(int j = i+1; j < n; j++)
- if(t2[i] + dist(x2[i], y2[i], x1[j], yyy[j]) < t1[j]) solver.G[i][j] = 1; // 至少要提前 1 分钟到达
- printf("%d\n", n - solver.solve());
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2945125.html