NO IMAGE

Description

作為一個旅行達人以及航空公司的金卡會員,你每一年的飛行里程可以繞赤道幾周了。你發現,航空公司為了提高飛機的使用率,並不是簡單的一條航線使用一架飛機來回飛,而是會讓同一架飛機連續不停地飛不同的航線,甚至有的時候為了能夠完成飛機的排程,航空公司還會增開一些臨時航線——在飛機轉場的同時順路捎一些乘客。你研究了一下GDOI著名航空公司GD Airways的常規直飛航線,你想知道,在最佳排程方案下,GD Airways最少需要多少架飛機才能成功執飛這所有的航線。

GDOI王國裡有N個機場,編號為1到N。從i號機場到j號機場需要飛行Ti,jT_{i,j}的時間。由於風向,地理位置和航空管制的因素,Ti,jT_{i,j}和Tj,iT_{j,i}並不一定相同。

此外,由於飛機降落之後需要例行維修和加油。當一架飛機降落kk號機場時,需要花費P[k]P[k]的維護時間才能再次起飛。

GD Airways一共運營MM條航線,其中第i條直飛航線需要在Di時刻從XiX_i機場起飛,不經停,飛往YiY_i機場。

為了簡化問題,我們假設GD Airways可以在00時刻在任意機場任意多架加油維護完畢的飛機;為了減少飛機的使用數,我們允許GD Airways增開任意多條臨時航線以滿足飛機的排程需要。

你想知道,理論上GD Airways最少需要多少架飛機才能完成所有這MM個航班。

Solution

維護時間只和降落的機場有關,所以我們可以直接把它加入飛行時間內

然而我們可以發現,直飛並不一定耗費最短時間,所以我們還需要做一遍最短路(這裡推薦大家打Floyd,SPFA跑完全圖嘛……,Floyd跑O(N3)O(N^3)實測是可以過的,SPFA反而超時,我就是被坑了

特別提醒:一開始給定你的航線是不可以走最短路的,因為

第i條直飛航線需要在Di時刻從XiX_i機場起飛,不經停

不經停!

這坑倒了無數人,包括我

繼續

我們可以把每個航班拆成兩個點,分別是出發和到達

點上記錄時刻和所在機場。

我們把到達的點和出發的點分別存在兩個陣列中

對於每一個到達點ii,時刻為Time[i]Time[i],所在機場為P[i]P[i],把所有的出發的點掃一遍,出發時刻設為Time[j]Time[j],所在機場為P[j]P[j]

把所有Time[i] dis[P[i]][P[j]]≤Time[j]{Time[i] dis[P[i]][P[j]]}\leq{Time[j]}的(i,j)(i,j)連一條邊

其中dis[i][j]dis[i][j]表示從ii號機場到jj號機場的時間

那麼我們可以得到一個二分圖,跑一遍最大匹配即可(建議打匈牙利)
不會匈牙利的戳這裡

http://blog.csdn.net/hzj1054689699/article/details/51035647

這是經典的路徑覆蓋問題

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define fo(i,a,b) for(i=a;i<=b;i  )
#define fod(i,a,b) for(i=a;i>=b;i--)
using namespace std;
struct note
{
int x,y,z;
};
bool cmp(note x,note y)
{
return x.y<y.y;
}
int dis[505][505],wh[501],map[505][505],n,m,a[505][505],dt[5005];
bool bz[505];
note l[505],r[505];
bool find(int k)
{
int i;
fo(i,1,a[k][0])
{
int p=a[k][i];
if (bz[p]==0)
{
bz[p]=1;
if (dt[p]==0||find(dt[p]))
{
dt[p]=k;
return 1;
}
}
}
return 0;
}
int main()
{
freopen("flight.in","r",stdin);
freopen("flight.out","w",stdout);
scanf("%d%d",&n,&m);
int i,j,k;
fo(i,1,n)
{
scanf("%d",&wh[i]);
}
fo(i,1,n)
{
fo(j,1,n)
{
scanf("%d",&map[i][j]);
if (i!=j) map[i][j] =wh[j]; 
dis[i][j]=map[i][j];
}   
}   
fo(k,1,n)
fo(i,1,n)
fo(j,1,n)
if (dis[i][j]>dis[i][k] dis[k][j])  dis[i][j]=dis[i][k] dis[k][j];
fo(i,1,m)
{
scanf("%d%d%d",&r[i].x,&l[i].x,&r[i].y);
l[i].y=r[i].y map[r[i].x][l[i].x];
l[i].z=r[i].z=i;
}
sort(l 1,l m 1,cmp);
sort(r 1,r m 1,cmp);
fo(i,1,m)
{
fo(j,1,m)
{
if (l[i].z!=r[j].z&&l[i].y dis[l[i].x][r[j].x]<=r[j].y) 
{
a[i][  a[i][0]]=j;
}
}
}
memset(dt,0,sizeof(dt));
int ans=m;
fo(i,1,m)
{
memset(bz,0,sizeof(bz));
if (find(i)) ans--; 
}
cout<<ans;
}