自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:14:13，当前版本为作者最后更新于2020-02-25 20:04:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题的建模思路有点神仙...

如果一架飞机在飞完第 $i$ 条航线后，能飞第 $j$ 条航线，就从 $i$ 向 $j$ 连一条有向边。

容易看出这个图是一张 DAG，我们的目标是用尽可能少的飞机飞完所有航线。

这是一个 DAG 上的最小路径覆盖 的模型。

现在问题来了，如何判断飞完第 $i$ 条航线后，是否能飞第 $j$ 条航线呢？

先预处理从 $i$ 机场出发，到 $j$ 机场且具备起飞条件的最短时间 $f(i,j)$。这个可以跑一遍 Floyd 实现。

设第 $i$ 条航线的起点为 $x_i$，终点为 $y_i$，起飞时间为 $d_i$，则同一架飞机飞完第 $i$ 条航线后能飞第 $j$ 条航线，当且仅当 $d_i+t(x_i,y_i)+p_{y_i}+f(y_i,x_j)\leq d_j$。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct graph
{
 struct edge
 {
  int v,w,next;
 }e[1000005];
 int s,t,cnt;
 int head[1005],cur[1005],dis[1005],vis[1005];
 void addedge(int u,int v,int w)
 {
  e[++cnt].v=v;
  e[cnt].w=w;
  e[cnt].next=head[u];
  head[u]=cnt;
 }
 void init(int S,int T)
 {
  s=S,t=T;
  memset(head,0,sizeof(head));
  cnt=1;
 }
 bool bfs()
 {
  queue<int> q;
  memset(dis,INF,sizeof(dis));
  memcpy(cur,head,sizeof(cur));
  dis[s]=0,vis[s]=1;
  q.push(s);
  while(!q.empty())
  {
   int u=q.front();
   q.pop();
   vis[u]=0;
   for(int i=head[u];i;i=e[i].next)
   {
    int v=e[i].v;
    if(e[i].w&&dis[v]>dis[u]+1)
    {
     dis[v]=dis[u]+1;
     if(!vis[v])q.push(v),vis[v]=1;
    }
   }
  }
  return dis[t]!=INF;
 }
 int dfs(int u,int flow)
 {
  if(u==t)return flow;
  int used=0;
  for(int i=cur[u];i;i=e[i].next)
  {
   int v=e[i].v;
   cur[u]=i;
   if(e[i].w&&dis[v]==dis[u]+1)
   {
    int f=dfs(v,min(flow-used,e[i].w));
    e[i].w-=f;
    e[i^1].w+=f;
    used+=f;
    if(used==flow)break;
   }
  }
  return used;
 }
 int maxflow()
 {
  int ans=0;
  while(bfs())
   ans+=dfs(s,INF);
  return ans;
 }
}g;
struct line
{
 int x,y,d;
}a[505];
int p[505],T[505][505],f[505][505];
int main()
{
 int n,m;
 cin>>n>>m;
 int s=2*m+1,t=2*m+2;
 g.init(s,t);
 for(int i=1;i<=n;i++)
  cin>>p[i];
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
   cin>>T[i][j];
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
   if(i!=j)f[i][j]=T[i][j]+p[j];
 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++)
 {
  cin>>a[i].x>>a[i].y>>a[i].d;
  g.addedge(s,i,1),g.addedge(i,s,0);
  g.addedge(i+m,t,1),g.addedge(t,i+m,0);
 }
 for(int i=1;i<=m;i++)
  for(int j=1;j<=m;j++)
  {
   int u=a[i].x,v=a[i].y,w=a[j].x;
   if(a[i].d+T[u][v]+p[v]+f[v][w]<=a[j].d)
    g.addedge(i,j+m,1),g.addedge(j+m,i,0);
  }
 cout<<m-g.maxflow()<<endl;
 return 0;
}