[洛谷 5769,loj 2077][JSOI2016]飞机调度

题目链接

https://www.luogu.com.cn/problem/P5769

https://loj.ac/problem/2077

题解

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

如果一架飞机在飞完第 \(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;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据