JZOJ-senior-5959. 【NOIP2018模拟11.8A组】铁路运输
Time Limits: 1000 ms Memory Limits: 262144 KB
Description
Input
Output
Sample Input
Sample Input1
5 6 5
1 2
1 3
4 2
3 2
2 5
5 3
5
2
4
1
3
Sample Input2
4 6 6
1 2
1 3
1 4
2 3
2 4
3 4
1
4
2
5
3
6
Sample Output
Sample Output1
0
2
2
4
4
Sample Output2
1
1
2
2
3
3
Data Constraint
Solution
据说是拓扑一下,我的可能大概也许是吧……
每个城市最早不满意的时间记为 ,每条边最早被修改的时间记为
每个点最早出现的时间就是它连向的点的最早不满意时间和当前这条边最早被修改的时间取
在它所连向的所有点的上面的操作取 即可
即
最后前缀和一下就好了
Code
#include<algorithm>
#include<cstdio>
#include<cctype>
#include<ctime>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define P(c) putchar(c)
using namespace std;
const int M=2e5+5,inf=1e9;
int n,m,q,num;
int v[M],p[M],dis[M],ans[M],last[M],d[10*M];
struct edge{int to,next,t;}e[2*M];
inline void read(int &n)
{
int x=0,w=0; char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
n=w?-x:x;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
void link(int x,int y)
{
e[++num]=(edge){y,last[x],q+1},last[x]=num;
}
void spfa()
{
fo(i,1,n) dis[i]=inf,v[i]=0;
int l=0,r=1; d[1]=1,dis[1]=0,v[1]=1;
while(l<r)
{
int x=d[++l]; v[x]=0;
for(int w=last[x];w;w=e[w].next)
{
int y=e[w].to;
if(dis[x]+1<dis[y])
{
dis[y]=dis[x]+1;
if(!v[y])
{
d[++r]=y,v[y]=1;
int x=rand()%(r-l)+l+1;
if(dis[d[x]]<dis[d[l+1]]) swap(d[x],d[l+1]);
}
}
}
}
}
void bfs()
{
fo(i,1,n) v[i]=0;
int l=0,r=1; d[1]=1,p[1]=q+1,v[1]=1;
while(l<r)
{
int x=d[++l];
for(int w=last[x];w;w=e[w].next)
{
int y=e[w].to;
if(dis[y]==dis[x]+1)
{
p[y]=max(p[y],min(p[x],e[w].t));
if(!v[y]) d[++r]=y,v[y]=1;
}
}
}
}
int main()
{
freopen("train.in","r",stdin);
freopen("train.out","w",stdout);
srand((unsigned)time(NULL));
read(n),read(m),read(q);
fo(i,1,m)
{
int x,y;
read(x),read(y);
link(x,y),link(y,x);
}
spfa();
fo(o,1,q)
{
int k;
read(k);
e[2*k-1].t=min(e[2*k-1].t,o);
e[2*k].t=min(e[2*k].t,o);
}
bfs();
fo(i,1,n) ++ans[p[i]];
fo(i,1,q) ans[i]+=ans[i-1],write(ans[i]),P('\n');
}