题目链接：
http://acm.hust.edu.cn/vjudge/problem/356788
Airports
Time Limit: 3000MS
#### 问题描述
> An airline company offers flights out of n airports, conveniently labeled
> from 1 to n. The flight time tij from airport i to airport j is known for
> every i and j. It may be the case that tij ̸= tji, due to things like wind
> or geography. Upon landing at a given airport, a plane must be inspected
> before it can be flown again. This inspection time pi
> is dependent only
> on the airport at which the inspection is taking place and not where the
> previous flight may have originated.
> Given a set of m flights that the airline company must provide, determine
> the minimum number of planes that the company needs to purchase. The airline may add
> unscheduled flights to move the airplanes around if that would reduce the total number of planes
> needed.
#### 输入
> The input file contains several test cases, each of them as described below.
> The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 500). The next
> line contains n space-separated integers p1, . . . , pn (0 ≤ pi ≤ 106
> ).
> Each of the next n lines contains n space-separated integers. The j-th integer in line i + 2 is tij
> (0 ≤ tij ≤ 106
> ). It is guaranteed that tii = 0 for all i. However, it may be the case that tij ̸= tji when
> i ̸= j.
> Each of the next m lines contains three space-separated integers, si
> , fi
> , and ti (1 ≤ si
> , fi ≤ n,
> si ̸= fi
> , 1 ≤ ti ≤ 106
> ), indicating that the airline company must provide a flight that flies out from
> airport si at exactly time ti
> , heading directly to airport fi
> .
#### 输出
> For each test case, print, on a single line, a single integer indicating the minimum number of planes the
> airline company must purchase in order to provide the m requested flights.
#### 样例
> **sample input**
> 2 2
> 1 1
> 0 1
> 1 0
> 1 2 1
> 2 1 1
> 2 2
> 1 1
> 0 1
> 1 0
> 1 2 1
> 2 1 3
> 5 5
> 72 54 71 94 23
> 0 443 912 226 714
> 18 0 776 347 810
> 707 60 0 48 923
> 933 373 881 0 329
> 39 511 151 364 0
> 4 2 174
> 2 1 583
> 4 3 151
> 1 4 841
> 4 3 993
>
> **sample output**
> 2
> 1
> 3
题意
给你一个有向图，有边权和点权，边权代表从u飞到v所需时间，点权p[i]表示如果飞机到达i点之后还要再起飞，那就需要p[i]时间的修整时间。
现在给你m趟航班要飞，每趟航班(u,v,t)表示从u飞到v，并且在u点的起飞时间是t。现在问你用最少的飞机跑完所有的航班。
题解
我们对每趟航班建一个点，如果飞机跑完一趟航班之后还能去跑另一趟航班，我们就连一条有向边，明显这样建出来的图是偏序图，也就是DAG，然后我们对这图跑一遍最小路径覆盖就可以了。
代码
#include<map>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define M (l+(r-l)/2)
#define bug(a) cout<<#a<<" = "<<a<<endl
using namespace std;
typedef __int64 LL;
const int maxn=555;
const int INF=0x3f3f3f3f;
int n,m;
int p[maxn];
int mat[maxn][maxn],f[maxn][maxn];
vector<int> G[maxn];
pair<int,int> a[maxn],b[maxn];
int vis[maxn],lef[maxn];
int match(int u){
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!vis[v]){
vis[v]=1;
if(lef[v]==-1||match(lef[v])){
lef[v]=u;
return true;
}
}
}
return false;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
//把点权直接合并到边权上
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&mat[i][j]);
if(i!=j) mat[i][j]+=p[j];
}
}
//预处理出最短路，用于判断两趟航班能不能用一架飞机跑
memcpy(f,mat,sizeof(mat));
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
//存每趟航班的两个属性
for(int i=1;i<=m;i++){
int u,v,t;
scanf("%d%d%d",&u,&v,&t);
a[i]=mkp(u,t);
b[i]=mkp(v,t+mat[u][v]);
}
//判断飞机跑完航班i，能不能继续飞航班j
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
if(i!=j&&b[i].Y+f[b[i].X][a[j].X]<=a[j].Y){
G[i].push_back(j);
}
}
}
//DAG的最小路径覆盖
memset(lef,-1,sizeof(lef));
int ans=0;
for(int i=1;i<=m;i++){
memset(vis,0,sizeof(vis));
if(match(i)) ans++;
}
ans=m-ans;
printf("%d
",ans);
return 0;
}
Notes
最小路径覆盖只能跑没有交叉的，比如1->2->3,4->2->5，这样有交叉的就会出问题，不过可以在建图的时候处理出1->2->3,4->5这样的东西，否则会出问题。