训练指南 UVALive - 3126（DAG最小路径覆盖）

时间：2022-12-15 07:11:33

layout: post

title: 训练指南 UVALive - 3126（DAG最小路径覆盖）

author: "luowentaoaa"

catalog: true

mathjax: true

tags:

- 二分图

- 图论

- 训练指南

- 最小路径覆盖

Taxi Cab Scheme

UVALive - 3126

题目大意：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;

}

相关文章