luogu1983 车站分级 (拓扑排序)

对每趟车建一个虚点p,对于不停车的x,连边(x,p,1);对于停车的y,连边(p,y,0)
有一条边(a,b,l)就是说b-a>=l
由于题目保证一定能走,直接拓扑序dp算最大的就行了

#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=2e3+,maxm=2e6+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Edge{
int b,l,ne;
}eg[maxm];
int egh[maxn],ect,N,M,f[maxn],ine[maxn];
queue<int> q; inline void adeg(int a,int b,int c){
eg[++ect].b=b,eg[ect].l=c,eg[ect].ne=egh[a],egh[a]=ect;
ine[b]++;
} int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd(),M=rd();
for(i=;i<=M;i++){
int p=N+i;
j=rd()-,k=rd();
adeg(p,k++,);
for(;j;j--){
int x=rd();
for(;k<x;k++)
adeg(k,p,);
adeg(p,k++,);
}
}
for(i=;i<=N+M;i++)
if(!ine[i]) q.push(i);
int ans=;
while(!q.empty()){
int p=q.front();q.pop();
for(i=egh[p];i;i=eg[i].ne){
int b=eg[i].b;ine[b]--;
f[b]=max(f[b],f[p]+eg[i].l);
ans=max(ans,f[b]);
if(!ine[b]) q.push(b);
}
}
printf("%d\n",ans+);
return ;
}
上一篇:android基础4——Mainifest


下一篇:查询分页的几种Sql写法