BZOJ 2535 Plane 航空管制2

http://www.lydsy.com/JudgeOnline/problem.php?id=2535

思路:对于1,我们只需要每个点比前驱大就可以了,然后满足尽量优。

对于第二问,我们先求出这个点前驱有几个,记为ans,cnt=ans

每访问一个未访问的点,cnt++

然后对于后面的点从少往大排,若有k>ans,那么一定在我们当前处理这个点前面,ans++

若有k<=cnt,说明要i放在这个点的后面,因此ans=k+1

记得不要省方便add(read(),read()),好像会出错。

 #include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
struct node{
int k,id;
}p[];
int tot=,go[],next[],first[];
int A[],n,m,vis[],cnt;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
void add(int x,int y){
insert(x,y);insert(y,x);
}
void init(){
n=read();m=read();
for (int i=;i<=n;i++) p[i].k=read(),p[i].id=i;
for (int i=;i<=m;i++){
int x=read(),y=read();
add(x,y);
}
}
bool cmp(node q,node w){
return q.k<w.k;
}
bool deal(int x){
for (int i=first[x];i;i=next[i]){
if (i&){
int pur=go[i];
p[x].k=std::min(p[x].k,p[pur].k-);
}
}
}
void solve1(){
for (int j=;j<=n;j++)
for (int i=;i<=n;i++)
deal(i);
std::sort(p+,p++n,cmp);
for (int i=;i<n;i++) printf("%d ",p[i].id);
printf("%d\n",p[n].id);
}
int count(int x){
int res=;vis[x]=;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (!vis[pur]&&(i%==)){
res+=count(pur);
}
}
return res+;
}
void solve2(){
for (int i=;i<=n;i++){
memset(vis,,sizeof vis);
int ans=count(i);
cnt=ans;
for (int j=;j<=n;j++)
if (!vis[p[j].id]){
cnt++;
if (p[j].k<=ans) ans++;
else if (cnt>p[j].k) ans=p[j].k+;
}
A[i]=ans;
}
for (int i=;i<n;i++) printf("%d ",A[i]);
printf("%d\n",A[n]);
}
void work(){
solve1();
solve2();
}
int main(){
init();
work();
}
上一篇:linux标准输入输出及错误输出


下一篇:2018-2019-2 《网络对抗技术》 Exp1 PC平台逆向破解 20165215