傳送門

首先（想了很久之后）注意到一個性質(zhì)：同一條邊有多種顏色的話保留3種就可以了，這是因為假如最優(yōu)解要求當前位置與相鄰兩條邊都不相同，那么只要有3條邊，就肯定可以滿足這一點。

完事就做一個nlogn*3^4的倍增dp就行了……實際肯定是跑不滿的（而且cc機子快）。

#include<cstdio> #include<cstring> #include<algorithm> #define MN 510000 using namespace std;int n,m,l[MN],F[MN][25],_F[MN][25],v[MN][25][3][3],num=0,x,y,w,C[MN][3],de[MN]; struct na{int y,w,ne; }b[MN<<2]; inline void add(int x,int y,int w){b[++num].y=y;b[num].w=w;b[num].ne=l[x];l[x]=num;} void dfs(int x,int f){if (F[x][0]) return;F[x][0]=x;F[x][1]=f;for (int i=2;i<25;i++)if (!(F[x][i]=F[F[F[x][i-1]][i-1]][1])) break;_F[x][0]=f;for (int i=1;i<25;i++)if (!(_F[x][i]=_F[_F[x][i-1]][i-1])) break;for (int i=l[x];i;i=b[i].ne)if (b[i].y!=f){dfs(b[i].y,x);if (!C[b[i].y][0]) C[b[i].y][0]=b[i].w;elseif (!C[b[i].y][1]) C[b[i].y][1]=b[i].w;elseif (!C[b[i].y][2]) C[b[i].y][2]=b[i].w;} } void DFS(int x,int f){if (de[x]) return;de[x]=de[f]+1;for (int a=0;a<3;a++)for (int b=0;b<3;b++)if (a!=b) v[x][0][a][b]=-1e8;int tmp1,tmp2,tmp3;for (int i=1;i<25;i++)if (_F[x][i])for (int a=0;a<3;a++)if (C[x][a])for (int b=0;b<3;b++)if (C[F[x][i]][b])for (int A=0;A<3;A++)if (C[F[x][i-1]][A])if ((tmp1=v[x][i-1][a][A])>=0)for (int B=0;B<3;B++)if (C[_F[x][i-1]][B])if ((tmp2=v[_F[x][i-1]][i-1][B][b])>=0)if (v[x][i][a][b]<(tmp3=tmp1+tmp2+(C[F[x][i-1]][A]!=C[_F[x][i-1]][B]))) v[x][i][a][b]=tmp3;for (int i=l[x];i;i=b[i].ne)if (b[i].y!=x) DFS(b[i].y,x); } inline int ask(int x,int y){if (de[x]>de[y]) swap(x,y);int ans[2][3],la[2];memset(ans,0,sizeof(ans));memset(la,0,sizeof(la));for (int i=24;i>=0;i--)if (de[_F[y][i]]>=de[x]){if (la[1]==0){for (int a=0;a<3;a++)for (int b=0;b<3;b++)if (ans[1][b]<v[y][i][a][b])ans[1][b]=v[y][i][a][b];la[1]=F[y][i];y=_F[y][i];}else{int tmp[3]={0,0,0},TMP;for (int a=0;a<3;a++)if (C[la[1]][a])for (int b=0;b<3;b++)if (C[y][b])for (int c=0;c<3;c++)if (C[F[y][i]][c])if (tmp[c]<(TMP=ans[1][a]+v[y][i][b][c]+(C[la[1]][a]!=C[y][b]))) tmp[c]=TMP;for (int a=0;a<3;a++) ans[1][a]=tmp[a];la[1]=F[y][i];y=_F[y][i];}}if (x==y){int tmp=0;for (int a=0;a<3;a++) if (ans[1][a]>tmp) tmp=ans[1][a];return tmp;}int st[2]={x,y};for (int i=24;i>=0;i--)if (_F[st[0]][i]!=_F[st[1]][i]){for (int j=0;j<2;j++){if (la[j]==0){for (int a=0;a<3;a++)for (int b=0;b<3;b++)if (ans[j][b]<v[st[j]][i][a][b])ans[j][b]=v[st[j]][i][a][b];la[j]=F[st[j]][i];st[j]=_F[st[j]][i];}else{int tmp[3]={-100000000,-100000000,-100000000},TMP;for (int a=0;a<3;a++)if (C[la[j]][a])for (int b=0;b<3;b++)if (C[st[j]][b])for (int c=0;c<3;c++)if (C[F[st[j]][i]][c])if (tmp[c]<(TMP=ans[j][a]+v[st[j]][i][b][c]+(C[la[j]][a]!=C[st[j]][b]))) tmp[c]=TMP;for (int a=0;a<3;a++) ans[j][a]=tmp[a];la[j]=F[st[j]][i];st[j]=_F[st[j]][i];}}}int i=0;for (int j=0;j<2;j++){if (la[j]==0){for (int a=0;a<3;a++)for (int b=0;b<3;b++)if (ans[j][b]<v[st[j]][i][a][b])ans[j][b]=v[st[j]][i][a][b];la[j]=F[st[j]][i];st[j]=_F[st[j]][i];}else{int tmp[3]={-100000000,-100000000,-100000000},TMP;for (int a=0;a<3;a++)if (C[la[j]][a])for (int b=0;b<3;b++)if (C[st[j]][b])for (int c=0;c<3;c++)if (C[F[st[j]][i]][c])if (tmp[c]<(TMP=ans[j][a]+v[st[j]][i][b][c]+(C[la[j]][a]!=C[st[j]][b]))) tmp[c]=TMP;for (int a=0;a<3;a++) ans[j][a]=tmp[a];la[j]=F[st[j]][i];st[j]=_F[st[j]][i];}}int tmp=0;for (int a=0;a<3;a++)for (int b=0;b<3;b++)if (tmp<ans[0][a]+ans[1][b]+(C[la[0]][a]!=C[la[1]][b])) tmp=ans[0][a]+ans[1][b]+(C[la[0]][a]!=C[la[1]][b]);return tmp; } int main(){scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&w);add(x,y,w);add(y,x,w);}dfs(1,0);DFS(1,0);//printf(">_<%d %d %d\n",C[3][0],C[3][1],C[3][2]);/*for (int i=1;i<=n;i++,puts("")){printf("%d:",i);for (int j=0;j<3;j++) printf("%d ",C[i][j]);}*/ //printf("%d %d\n",v[6][2][0][0],_F[6][2]);scanf("%d",&m);while(m--){scanf("%d%d",&x,&y);printf("%d\n",ask(x,y));} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Enceladus/p/9427433.html

總結(jié)

以上是生活随笔為你收集整理的Codechef July Challenge 2018 : Subway Ride的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。