目录
显示
题目链接
https://www.luogu.com.cn/problem/P5769
题解
这题的建模思路有点神仙…
如果一架飞机在飞完第 \(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;
}