YZOJ P2791 商人
时间限制：2000MS 内存限制：262144KB
难度：\(6.0\)
是一个裸的广义圆方树，原图中两点简单路径等于圆方树上两点简单路径。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #undef INT_MAX #define INT_MAX 0x7F7F7F7F #define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_)) inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } #define ReverseEdge(_x) ((_x)&1 ? (_x)+1 : (_x)-1) int gcnto,gheado[305050],gnexto[2050505],gnodeo[2050505]; inline void insertLineO(register int s,register int t) { gnexto[++gcnto]=gheado[s],gheado[s]=gcnto,gnodeo[gcnto]=t; gnexto[++gcnto]=gheado[t],gheado[t]=gcnto,gnodeo[gcnto]=s; } int gcnt,ghead[605050],gnext[5505050],gnode[5505050]; inline void insertLine(register int s,register int t) { gnext[++gcnt]=ghead[s],ghead[s]=gcnt,gnode[gcnt]=t; gnext[++gcnt]=ghead[t],ghead[t]=gcnt,gnode[gcnt]=s; //printf("%d <-> %d\n",s,t); } int c[605050]; int tcnt,dcnt,dfn[305050],low[305050],stk[305050],top; void Tarjan(register int o,register int fj) { dfn[o]=low[o]=++dcnt,stk[++top]=o; for(register int j=gheado[o],t;j;j=gnexto[j]) if(!dfn[t=gnodeo[j]]) { Tarjan(t,ReverseEdge(j)); low[o]=_min(low[o],low[t]); if(low[t] >= dfn[o]) { c[++tcnt]=_min(c[o],c[t]); while(top && stk[top] != t) c[tcnt]=_min(c[tcnt],c[stk[top]]),insertLine(stk[top--],tcnt); insertLine(t,tcnt),insertLine(o,tcnt); top--; } } else if(j != fj) low[o]=_min(low[o],dfn[t]); } int _log[605050],depth[605050],f[605050][22],cf[605050][22]; void DFS(register int o,register int fa) { for(register int j=ghead[o],t;j;j=gnext[j]) if((t=gnode[j]) != fa) { depth[t]=depth[o]+1; f[t][0]=o,cf[t][0]=_min(cf[t][0],c[o]); DFS(t,o); } } int main() { register int N=getnum(),M=getnum(),Q=getnum(); memset(cf,0x7F,sizeof(cf)),tcnt=N; for(register int i=1;i<=N;i++) cf[i][0]=c[i]=getnum(); for(register int i=1;i<=M;i++) insertLineO(getnum(),getnum()); Tarjan(1,0),N=tcnt; depth[1]=1,DFS(1,0); for(register int i=2;i<=N;i++) _log[i]=_log[i>>1]+1; for(register int k=1;k<=_log[N];k++) for(register int i=1;i<=N;i++) { f[i][k]=f[f[i][k-1]][k-1]; cf[i][k]=_min(cf[i][k-1],cf[f[i][k-1]][k-1]); } for(register int lp=1;lp<=Q;lp++) { register int s=getnum(),t=getnum(),v=getnum(),cmn=_min(c[s],c[t]); if(depth[s] > depth[t]) s^=t^=s^=t; //printf("from %d\n",t); register int df=depth[t]-depth[s]; for(register int k=0;k<=_log[df];k++) if(df&(1<<k)) cmn=_min(cmn,cf[t][k]),t=f[t][k]; //printf("get %d %d %d\n",s,t,cmn); if(s != t) { for(register int k=_log[N];k>=0;k--) if(f[s][k] != f[t][k]) { cmn=_min(cmn,_min(cf[s][k],cf[t][k])); s=f[s][k],t=f[t][k]; //printf("next %d %d\n",s,t); } cmn=_min(cmn,_min(cf[s][0],cf[t][0])); s=f[s][0]; } printf("%lld\n",(long long)cmn*v); } return 0; } |