飞机调度[JSOI2016]

发表于 分类于 ， ，

题目

bzoj

loj

题解

考虑一架飞机，飞了某个航班后，还能飞哪个航班。

假设把一条航班看做点，能从航班 $i$ 到达航班 $j$ 的连一条有向边 $(i,j)$，则航班之间形成了一个 DAG。

则我们只需要求这个DAG的最小路径覆盖，这十分模板。

现在只需考虑两个航班 $i,j$ 之间是否存在有向边。那就是 $i$ 飞完后，在航班 $i$ 的中点加完油后，再沿着最短路飞往 $j$ 的起点，看时间是否赶得上。

因此只需求出两点间最短路径，Floyd 即可。

时间复杂度 $O(n^3)$，假设 $n,m$ 同阶。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <complex>
#include <utility>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>
//#include <unordered_set>
//#include <unordered_map>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define com complex<db>
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&(-(x)))
#define bit(x,i) (((x)>>(i))&1)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=1005;
const int M=1300010;
const int inf=1e9;
namespace Dinic{
	int s,t;
	int ver[M],val[M],ne[M],head[N],tot=1;
	queue<int> q;
	int d[N],cur[N];
	inline void add(int x,int y,int z)
	{
		ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=0; ne[tot]=head[y]; head[y]=tot;
	}
	bool bfs()
	{
		for(;!q.empty();q.pop());
		fo(i,s,t) d[i]=0;
		q.push(s); d[s]=1;
		for(;!q.empty();)
		{
			int u=q.front(); q.pop();
			for(int i=head[u],v;i;i=ne[i])
				if(d[v=ver[i]]==0&&val[i])
				{
					d[v]=d[u]+1;
					q.push(v);
					if(v==t) return 1;
				}
		}
		return 0;
	}
	int dfs(int u,int flow)
	{
		if(u==t||!flow) return flow;
		int res=flow,r;
		for(int &i=cur[u],v;i&&res;i=ne[i])
			if(d[v=ver[i]]==d[u]+1&&val[i])
			{
				r=dfs(v,min(res,val[i]));
				if(!r) continue;
				res-=r;
				val[i]-=r; val[i^1]+=r;
			}
		return flow-res;
	}
	int dinic()
	{
		int flow=0;
		for(;bfs();)
		{
			fo(i,s,t) cur[i]=head[i];
			flow+=dfs(s,inf);
		}
		return flow;
	}
}
using Dinic::s;
using Dinic::t;
using Dinic::dinic;
using Dinic::add;
const int K=505;
int n,m;
int tim[K][K],f[K][K],d[K],p[K],x[K],y[K];
inline int check(int i,int j)
{
	return d[i]+tim[x[i]][y[i]]+p[y[i]]+f[y[i]][x[j]]<=d[j];
}
int main()
{
	n=read(); m=read();
	fo(i,1,n) p[i]=read();
	fo(i,1,n) fo(j,1,n) tim[i][j]=read(),f[i][j]=tim[i][j]+p[j];
	fo(i,1,n) f[i][i]-=p[i];
	fo(k,1,n) fo(i,1,n) fo(j,1,n)
		if(f[i][j]>f[i][k]+f[k][j])
			f[i][j]=f[i][k]+f[k][j];
	fo(i,1,m) x[i]=read(),y[i]=read(),d[i]=read();
	s=0; t=2*m+1;
	fo(i,1,m) add(s,i,1),add(i+m,t,1);
	fo(i,1,m) fo(j,1,m)
		if(i!=j&&check(i,j))
			add(i,j+m,1);
	printf("%d\n",m-dinic());
	return 0;
}