返回信息流Description
With human lives at stake, an air traffic controller has to schedule the airplanes that are landing at an airport in order to avoid airplane collision. Each airplane ii has a time window [si,ti] during which it can safely land. You must compute the exact time of landing for each airplane that respects these time windows. Furthermore, the airplane landings should be stretched out as much as possible so that the minimum time gap between successive landings is as large as possible.
For example, if the time window of landing three airplanes are [10:00-11:00], [11:20-11:40], [12:00-12:20], and they land at 10:00, 11:20, 12:20 respectively, then the smallest gap is 60 minutes, which occurs between the last two airplanes.
Given 5 time windows, denoted as [s1,t1],[s2,t2],...,[s5,t5] satisfying 0<=s1<t1<s2<t2<...<s5<t5<=24. You are required to give the exact landing time of each airplane, in which the smallest gap between successive landings is maximized.
Input
10 numbers(type is double) s1,t1,s2,t2,...,s5,t5, satisfying 0<=s1<t1<s2<t2<...<s5<t5<=24.
Output
5 numbers(type is double) l1,l2,...,l5, with accuracy of two decimal digits.
Sample Input
1 2 3 4 5 6 7 8 9 10
Sample Output
1.00 3.25 5.50 7.75 10.00
小弟在此谢过各位大佬！！拜谢！！
------------------------
感谢SCOUT大佬！第一个问题已解决！
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #97363同步于 2018/12/11
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【求助】线性规划还是二分搜索？
LittleHorse
2018/12/11镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
# include<iostream>
# include<cstdio>
# include<cstring>
# include<queue>
using namespace std;
const int MAX=2e6+1,INF=1e7,t=2e6;
struct p{
int x,y,dis,cn;
}c[MAX<<2];
int n,m,num,tot1;
int d[MAX],h[MAX],pre[MAX];
bool use[MAX];
void add(int x,int y,int dis,int cn)
{
c[num].x=h[y],c[num].y=x,c[num].dis=0,c[num].cn=-cn,h[y]=num++;
c[num].x=h[x],c[num].y=y,c[num].dis=dis,c[num].cn=cn,h[x]=num++;
}
void EK()
{
while(1)
{
queue<int> qu;
qu.push(0);
memset(pre,0,sizeof(pre));
memset(d,1,sizeof(d));
d[0]=0;
while(!qu.empty())
{
int tt=qu.front();
qu.pop();
use[tt]=0;
for(int i=h[tt];i;i=c[i].x)
if(c[i].dis&&d[c[i].y]>d[tt]+c[i].cn)
{
d[c[i].y]=d[tt]+c[i].cn;
pre[c[i].y]=i;
if(!use[c[i].y])
{
use[c[i].y]=1;
qu.push(c[i].y);
}
}
}
if(d[t]>INF) return;
int sum=INF,hh=t;
while(pre[hh])
{
int l=pre[hh];
sum=min(sum,c[l].dis);
hh=c[l^1].y;
}
hh=t;
while(pre[hh])
{
int l=pre[hh];
c[l].dis-=sum;
c[l^1].dis+=sum;
tot1+=sum*c[l].cn;
hh=c[l^1].y;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
add(i,i+1,INF-x,0);
}
add(0,1,INF,0);
add(n+1,t,INF,0);
for(int i=1;i<=m;i++)
{
int x,y,dis;
scanf("%d%d%d",&x,&y,&dis);
add(x,y+1,INF,dis);
}
EK();
printf("%d",tot1);
return 0;
}
【 在 SCOUT 的大作中提到: 】
: # include<iostream>
: # include<cstdio>
: # include<cstring>
: ...................
大佬好稳！！！好好学习一下大佬的代码
【 在 SCOUT 的大作中提到: 】
: # include<iostream>
: # include<cstdio>
: # include<cstring>
: ...................
请问大佬第二题有么有思路，有思路的话可以拜托您给我说一下吗？