此博客停更

12
18
2015

0

[bzoj]2750: [HAOI2012]Road

-->http://www.lydsy.com/JudgeOnline/problem.php?id=2750

不说什么了，n遍spfa然后Dp

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1550
#define ll long long
int i,j,k,m,n,x,y,cnt,last[N],dis[N],d[N],a[N],b[N];ll ans[50050];
struct edge{int from,to,next,v;}e[50050];bool vis[N];
inline void add(int w,int v,int u){e[++cnt]=(edge){u,v,last[u],w},last[u]=cnt;}
#define met(x,y) memset(x,y,sizeof x)
inline void spfa(int s){
	queue<int>q;met(dis,0x3f),met(vis,0),dis[s]=0,q.push(s);
	while(!q.empty()){
		int k=q.front();q.pop(),vis[k]=1;
		for(int i=last[k],y;i;i=e[i].next)if(dis[y=e[i].to]>dis[k]+e[i].v){
			dis[y]=dis[k]+e[i].v;
			if(!vis[y])vis[y]=1,q.push(y);
		}vis[k]=0;
	}
}
#define mo 1000000007
inline void ad(int&a,int b){a+=b;if(a>=mo)a-=mo;}
inline void ad(ll&a,ll b){a+=b;if(a>=mo)a-=mo;}
void dfs1(int x){vis[x]=1;for(int i=last[x],y;i;i=e[i].next)if(dis[y=e[i].to]==dis[x]+e[i].v){++d[y];if(!vis[y])dfs1(y);}}
void dfs2(int x){for(int i=last[x],y;i;i=e[i].next)if(dis[y=e[i].to]==dis[x]+e[i].v){ad(a[y],a[x]);if(!(--d[y]))dfs2(y);}}
void dfs3(int x){b[x]=1;for(int i=last[x],y;i;i=e[i].next)if(dis[y=e[i].to]==dis[x]+e[i].v){if(!b[y])dfs3(y);ad(b[x],b[y]);}}
int main(){
	for(n=read(),m=read(),i=1;i<=m;++i)add(read(),read(),read());
	for(i=1;i<=n;++i){
		spfa(i),met(vis,0),met(a,0),met(b,0),met(d,0);
		dfs1(i),a[i]=1,dfs2(i),dfs3(i);
		for(j=1;j<=m;++j)if(dis[e[j].from]+e[j].v==dis[e[j].to])ad(ans[j],1ll*a[e[j].from]*b[e[j].to]);
	}
	for(i=1;i<=m;++i)printf("%lld\n",ans[i]);
}

Category: bzoj | Tags: 最短路 DP

12
18
2015

0

[bzoj]3064: Tyvj 1518 CPU监控

-->http://www.lydsy.com/JudgeOnline/problem.php?id=3064

线段树裸题，维护六个标记，当前最大值，当前加标记，当前覆盖标记，历史最大值，历史最大加标记，历史最大覆盖标记。

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define oo -0x7f7f7f7f
#define nc() getchar()
inline int read(){
	int x=0,f=1;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}inline void read(char&c){for(c=nc();c==' '||c=='\n';c=nc());}
#define N 100010
int i,j,k,m,n,x,y,a[N],L,R,V,q;bool F;
struct tree{int mx,cover,ad,pmx,pcover,pad;}T[N<<2];
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
#define max(a,b) ((a)>(b)?(a):(b))
inline void Mx(int&a,int b){if(b>a)a=b;}
#define up(k) (T[k].mx=max(T[k<<1].mx,T[k<<1|1].mx),Mx(T[k].pmx,max(T[k<<1].pmx,T[k<<1|1].pmx)))
void build(int k,int l,int r){
	T[k].cover=T[k].pcover=oo;
	if(l==r){T[k].mx=T[k].pmx=a[l];return;}
	int m=l+r>>1;build(lson),build(rson),T[k].pmx=oo,up(k);
}
#define Pcover(k,v) (Mx(T[k].pmx,v),Mx(T[k].pcover,v))
#define Pad(k,v) (Mx(T[k].pmx,T[k].mx+v),T[k].cover>oo?Mx(T[k].pcover,T[k].cover+v):Mx(T[k].pad,T[k].ad+v))
#define Cover(k,v) (Mx(T[k].pmx,T[k].mx=v),Mx(T[k].pcover,T[k].cover=v),T[k].ad=0)
#define Ad(k,v) (Mx(T[k].pmx,T[k].mx+=v),T[k].cover>oo?Mx(T[k].pcover,T[k].cover+=v):Mx(T[k].pad,T[k].ad+=v))
inline void down(int k){
	if(T[k].pad)Pad(k<<1,T[k].pad),Pad(k<<1|1,T[k].pad),T[k].pad=0;
	if(T[k].pcover>oo)Pcover(k<<1,T[k].pcover),Pcover(k<<1|1,T[k].pcover),T[k].pcover=oo;
	if(T[k].ad)Ad(k<<1,T[k].ad),Ad(k<<1|1,T[k].ad),T[k].ad=0;
	if(T[k].cover>oo)Cover(k<<1,T[k].cover),Cover(k<<1|1,T[k].cover),T[k].cover=oo;
}
int ask(int k,int l,int r){
	if(L<=l&&R>=r)return F?T[k].pmx:T[k].mx;down(k);
	int m=l+r>>1,ans=oo;
	if(L<=m)Mx(ans,ask(lson));
	if(R>m)Mx(ans,ask(rson));return up(k),ans;
}
void change(int k,int l,int r){
	if(L<=l&&R>=r){if(F)Cover(k,V);else Ad(k,V);return;}down(k);
	int m=l+r>>1;if(L<=m)change(lson);if(R>m)change(rson);up(k);
}
int main(){
	for(n=read(),i=1;i<=n;++i)a[i]=read();
	for(build(1,1,n),q=read();q--;){
		char f;read(f),L=read(),R=read();
		if(f=='Q')F=0,printf("%d\n",ask(1,1,n));
		else if(f=='A')F=1,printf("%d\n",ask(1,1,n));
		else if(f=='P')F=0,V=read(),change(1,1,n);
		else F=1,V=read(),change(1,1,n);
	}
}

Category: bzoj | Tags: 线段树

12
17
2015

2