题解 P5769 【[JSOI2016]飞机调度】
xtx1092515503
·
·
题解
我爱网络流
刚看到这道题一点思路也没有，后来想一想就想明白了。
首先，为了找出每个航班之间能否转移的关系，我们可以建立一个dis_{i,j}数组，表示从点i到点j并能够再次起飞的最短时间。
由题意，我们可以初始dis_{i,j}=T_{i,j}+P_j，表示一开始的航班都是直飞的。另外，如果i=j，则必有dis_{i,j}=0。
然后在dis上跑floyd。这样就完成了dis数组的求解。
如果在一个航班结束后，按照最短路径（即dis），能够按时赶上另一个航班，则它们可以转移。
设航班i是从点x_i到点y_i，时间是从s_i到t_i，则如果有：
**另，$t_i=s_i+T_{x_i,y_i}+P_{y_i}$，而不是$t_i=s_i+dis_{x_i,y_i}$，因为航班是直飞，不是按照最短路径飞！**~~我为了这个一直WA30。~~
在转移关系建好之后，我们来观察一下现在的状况：
我们有$m$条航班，航班之间互有有向的转移关系，但转移关系保证无环（因为按时间转移）。
这让人想到了什么？
[最小路径覆盖问题](https://www.luogu.com.cn/problem/P2764)！！！
~~不会的人，推一下我的[网络流blog](https://www.luogu.com.cn/blog/Troverld/wang-lao-liu-xue-xi-bi-ji)。第一题就是它。~~
代码：
```cpp
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int n,m,fix[510],dis[510][510],dd[510][510];
struct AirLine{
int u,v,s,t;
}a[510];
int head[1010],cur[1010],dep[1010],cnt,S,T,res;
struct node{
int to,next,val;
}edge[4010000];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
}
queue<int>q;
inline bool bfs(){
memset(dep,0,sizeof(dep)),q.push(S),dep[S]=1;
while(!q.empty()){
register int x=q.front();q.pop();
for(register int i=cur[x]=head[x];i!=-1;i=edge[i].next)if(edge[i].val&&!dep[edge[i].to])dep[edge[i].to]=dep[x]+1,q.push(edge[i].to);
}
return dep[T]>0;
}
bool reach;
inline int dfs(int x,int flow){
if(x==T){
res+=flow;
reach=true;
return flow;
}
int used=0;
for(register int &i=cur[x];i!=-1;i=edge[i].next){
if(!edge[i].val||dep[edge[i].to]!=dep[x]+1)continue;
register int ff=dfs(edge[i].to,min(edge[i].val,flow-used));
if(ff){
edge[i].val-=ff;
edge[i^1].val+=ff;
used+=ff;
if(used==flow)break;
}
}
return used;
}
inline void Dinic(){
while(bfs()){
reach=true;
while(reach)reach=false,dfs(S,0x3f3f3f3f);
}
}
int main(){
scanf("%d%d",&n,&m),memset(head,-1,sizeof(head)),S=2*m+1,T=2*m+2;
for(int i=1;i<=n;i++)scanf("%d",&fix[i]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&dd[i][j]),dis[i][j]=(i==j?0:dd[i][j]+fix[j]);
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].s),a[i].t=a[i].s+dd[a[i].u][a[i].v]+fix[a[i].v];
for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(a[i].t+dis[a[i].v][a[j].u]<=a[j].s)ae(i,j+m,1);
for(int i=1;i<=m;i++)ae(S,i,1),ae(i+m,T,1);
Dinic();
printf("%d\n",m-res);
return 0;
}
```