网站开发的原理,商务型网站建设,网站开发和后台维护,阿里巴巴上怎样做自己的网站Description 给一个N个点M条边的连通无向图#xff0c;满足每条边最多属于一个环#xff0c;有Q组询问#xff0c;每次询问两点之间的最短路径。 Input 输入的第一行包含三个整数#xff0c;分别表示N和M和Q 下接M行#xff0c;每行三个整数v#xff0c;u#xff0c;w表…Description 给一个N个点M条边的连通无向图满足每条边最多属于一个环有Q组询问每次询问两点之间的最短路径。 Input 输入的第一行包含三个整数分别表示N和M和Q 下接M行每行三个整数vuw表示一条无向边v-u长度为w 最后Q行每行两个整数vu表示一组询问 Output 输出Q行每行一个整数表示询问的答案 Sample Input 9 10 2 1 2 1 1 4 1 3 4 1 2 3 1 3 7 1 7 8 2 7 9 2 1 5 3 1 6 4 5 6 1 1 9 5 7 Sample Output 5 6 HINT 对于100%的数据N10000Q10000 这题写的我真TM舒服…… 首先对仙人掌建出一棵圆方树考虑树上的边权如果是圆点连圆点则边权不变如果是圆点连方点则边权为圆点到方点所属环上dfs序最小的点的距离 然后我们考虑lca的两种情况如果lca是圆点那么我们直接输出圆方树上的两点之间距离如果lca是方点我们找到\(x,y\)在lca儿子中的祖先节点\(x,y\)则答案为\(dis_{x\rightarrow x}dis_{x\rightarrow y}dis_{y\rightarrow y}\) 树剖求lca找\(x,y\)时细节贼难受…… /*program from Wolfycz*/
#includecmath
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define Fi first
#define Se second
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pairint,intpii;
typedef unsigned long long ull;
inline char gc(){static char buf[1000000],*p1buf,*p2buf;return p1p2(p2(p1buf)fread(buf,1,1000000,stdin),p1p2)?EOF:*p1;
}
inline int frd(){int x0,f1; char chgc();for (;ch0||ch9;chgc()) if (ch-) f-1;for (;ch0ch9;chgc()) x(x3)(x1)ch-0;return x*f;
}
inline int read(){int x0,f1; char chgetchar();for (;ch0||ch9;chgetchar()) if (ch-) f-1;for (;ch0ch9;chgetchar()) x(x3)(x1)ch-0;return x*f;
}
inline void print(int x){if (x0) putchar(-),x-x;if (x9) print(x/10);putchar(x%100);
}
const int N1e4;
int V[N10],cnt,n,m,q;
struct node{int lca,x,y;node(){lcaxy0;}node(int _l,int _x,int _y){lca_l,x_x,y_y;}void insert(int _l,int _x,int _y){lca_l,x_x,y_x;}
};
struct S1{ int pre[(N2)10],now[(N1)10],child[(N2)10],val[(N2)10],tot;int fa[(N1)10],deep[(N1)10],top[(N1)10],Rem[(N1)10],size[(N1)10],dis[(N1)10];void join(int x,int y,int z){pre[tot]now[x],now[x]tot,child[tot]y,val[tot]z;}void insert(int x,int y,int z){join(x,y,z),join(y,x,z);}void dfs(int x){deep[x]deep[fa[x]]1,size[x]1;for (int pnow[x],sonchild[p];p;ppre[p],sonchild[p]){if (sonfa[x]) continue;fa[son]x,dis[son]dis[x]val[p];dfs(son),size[x]size[son];if (size[Rem[x]]size[son]) Rem[x]son;}}void build(int x){if (!x) return;top[x]Rem[fa[x]]x?top[fa[x]]:x;build(Rem[x]);for (int pnow[x],sonchild[p];p;ppre[p],sonchild[p]){if (sonfa[x]||sonRem[x]) continue;build(son);}}node LCA(int x,int y){int lastx0,lasty0;while (top[x]!top[y]){if (deep[top[x]]deep[top[y]]) lastytop[y],yfa[top[y]];else lastxtop[x],xfa[top[x]];}if (xy) return node(x,lastx,lasty);if (deep[x]deep[y]) return node(x,lastx,Rem[x]);else return node(y,Rem[y],lasty);//WA了好几次画了图才发现应该这样写……}
}RST;//Round Square Tree
struct S2{int pre[(N2)10],now[N10],child[(N2)10],val[(N2)10];int fa[N10],dfn[N10],low[N10],fv[N10],dis[N10],stack[N10],belong[N10];bool instack[N10];int tot,Time,top,num;void join(int x,int y,int z){pre[tot]now[x],now[x]tot,child[tot]y,val[tot]z;}void insert(int x,int y,int z){join(x,y,z),join(y,x,z);}int distant(int x,int y,int pos){if (dfn[x]dfn[y]) swap(x,y);return min(dis[x]-dis[y],V[pos]-(dis[x]-dis[y]));}void dfs(int x){dfn[x]Time;for (int pnow[x],sonchild[p];p;ppre[p],sonchild[p]){if (sonfa[x]) continue;if (!dfn[son]){fa[son]x,dis[son]dis[x]val[p];fv[son]val[p],dfs(son);}else if (dfn[son]dfn[x]){V[cnt]val[p],RST.insert(cntn,son,0);for (int ix;i!son;ifa[i]) V[cnt]fv[i];for (int ix;i!son;ifa[i]) RST.insert(cntn,i,distant(i,son,cnt));}}}void tarjan(int x,int fa){//不论如何枚举顺序都是一样的那么dfn就算再次dfs也是一样的dfn[x]low[x]Time;instack[stack[top]x]1;for (int pnow[x],sonchild[p];p;ppre[p],sonchild[p]){if (sonfa) continue;if (!dfn[son]) tarjan(son,x),low[x]min(low[x],low[son]);else if (instack[son]) low[x]min(low[x],dfn[son]);}if (dfn[x]low[x]){belong[x]num;instack[x]0;while (stack[top]!x) belong[stack[top]]num,instack[stack[top--]]0;top--;}}void init(){Time0;memset(dfn,0,sizeof(dfn));}
}OT;//Original Tree
struct S3{int x,y,z;void insert(int _x,int _y,int _z){x_x,y_y,z_z;}
}Line[(N1)10];
int main(){nread(),mread(),qread();for (int i1;im;i){int xread(),yread(),zread();OT.insert(x,y,z);Line[i].insert(x,y,z);}OT.dfs(1),OT.init(),OT.tarjan(1,0);for (int i1;im;i)if (OT.belong[Line[i].x]!OT.belong[Line[i].y])RST.insert(Line[i].x,Line[i].y,Line[i].z);RST.dfs(1),RST.build(1);for (int i1;iq;i){int xread(),yread();node tmpRST.LCA(x,y);if (tmp.lcan) printf(%d\n,RST.dis[x]RST.dis[y]-2*RST.dis[tmp.lca]);else{int resRST.dis[x]RST.dis[y]-RST.dis[tmp.x]-RST.dis[tmp.y];resOT.distant(tmp.x,tmp.y,tmp.lca-n);printf(%d\n,res);}}return 0;
} 转载于:https://www.cnblogs.com/Wolfycz/p/10279492.html
