Instantly share code, notes, and snippets.

# zrt/bzoj2725_zrt Created Aug 3, 2014

BZOJ 2725 : [Violet 6]故乡的梦
 /************************************************************** Problem: 2725 User: zrts Language: C++ Result: Accepted Time:13512 ms Memory:49700 kb ****************************************************************/ #include #include #include #include #include #include #include //by zrt //problem: using namespace std; typedef long long LL; const LL inf(0x3f3f3f3f3f3f3f3fLL); const double eps(1e-9); int H0[200005],X0[400005],P0[400005],tot0,E0[400005]; void add0(int x,int y,int z){ P0[++tot0]=y;X0[tot0]=H0[x];H0[x]=tot0;E0[tot0]=z; } int H1[200005],X1[400005],P1[400005],tot1,flow[400005],from[400005],E1[400005]; void add1(int x,int y,int z){ P1[++tot1]=y;X1[tot1]=H1[x];H1[x]=tot1;flow[tot1]=z;from[tot1]=x; } int H2[200005],X2[400005],P2[400005],tot2,E2[400005],from2[400005]; void add2(int x,int y,int z){ P2[++tot2]=y;X2[tot2]=H2[x];H2[x]=tot2;E2[tot2]=z;from2[tot2]=x; } int n,m,Q,S,T; int cut[200005]; LL ds[200005],dt[200005]; bool vis[200005]; struct N{ int x;LL w; N(int a=0,LL b=0){ x=a,w=b; } friend bool operator < (N a,N b){ return a.w>b.w; } }; priority_queue q; int d[200005]; queue qu; deque dq; bool bfs(){ memset(d,0,sizeof d); d[S]=1;int x;qu.push(S); while(!qu.empty()){ x=qu.front();qu.pop(); if(x==T) continue; for(int i=H1[x];i;i=X1[i]){ if(flow[i]>0&&!d[P1[i]]){ d[P1[i]] =d[x]+1; qu.push(P1[i]); } } } return d[T]; } int dfs(int x,int a){ if(x==T||a==0) return a; int tmp,f=a; for(int i=H1[x];i;i=X1[i]){ if(flow[i]>0&&d[P1[i]]==d[x]+1){ tmp=dfs(P1[i],min(flow[i],a)); a-=tmp; flow[i]-=tmp; flow[i^1]+=tmp; if(!a) break; } } if(a==f) d[x]=-1; return f-a; } int ff; int low[200005],tim; int stk[200005],top; bool instk[200005]; int id[200005]; int cnt; void tarjan(int x){ stk[top++]=x;instk[x]=1; int dfn=low[x]=++tim; for(int i=H1[x];i;i=X1[i]){ if(flow[i]==0) continue; if(!low[P1[i]]){ tarjan(P1[i]); low[x]=min(low[x],low[P1[i]]); }else if(instk[P1[i]]) low[x]=min(low[x],low[P1[i]]); } if(dfn==low[x]){ cnt++; int k; do{ k=stk[--top]; instk[k]=0; id[k]=cnt; }while(k!=x); } } int Ds[200005],Dt[200005]; LL ans[200005]; vector v[200005]; struct A{ int x,y; LL w; A(int a=0,int b=0,LL c=0){ x=a,y=b,w=c; } friend bool operator < (A a,A b){ return a.w>b.w; } }; priority_queue pq; int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif tot0=tot1=1; scanf("%d%d",&n,&m); for(int i=0,x,y,z;ids[x]+E0[i]){ ds[P0[i]]=ds[x]+E0[i]; q.push(N(P0[i],ds[P0[i]])); } } } memset(vis,0,sizeof vis); q.push(N(T,0)); while(!q.empty()){ x=q.top().x;q.pop(); if(vis[x]) continue; vis[x]=1; if(x==S) continue;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1 for(int i=H0[x];i;i=X0[i]){ if(!vis[P0[i]]&&dt[P0[i]]>dt[x]+E0[i]){ dt[P0[i]]=dt[x]+E0[i]; q.push(N(P0[i],dt[P0[i]])); } } } if(ds[T]==inf) { for(int i=0;i=Ds[T]-num) pq.pop(); for(int j=0;jnum&&cut[x]!=P0[i]) pq.push(A(x,P0[i],ds[x]+E0[i]+dt[P0[i]])); } } int xx,yy; if(!pq.empty()) xx=pq.top().x,yy=pq.top().y,ans[num]=pq.top().w; } for(int i=0,x,y;i
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.