目录
显示
题目链接
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; }