/*这个小专题还蛮有意思 融入了一些游戏元素 读起来的时候真想玩几盘*/
刺客信条
–这道题可以用二分，或者是并查集
但是怎么写check（）是个大问题
首先，你可以发现，对于一个人，他能控制的范围是个圆
如果不能到终点的情况就是一串圆相连，把起点和终点隔开
所以可以用并查集维护连通性
当边界刚好联通的那个就是最远的距离
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int MAXN=2005; int x,y,n; int a[MAXN],b[MAXN]; struct hehe{ int u,v; long long l; }edge[MAXN*MAXN]; int cnt; int f[MAXN]; long long ans; void add_1(int i){ cnt++; edge[cnt].u=i; edge[cnt].v=n+1; edge[cnt].l=1ll*min(a[i],y-b[i])*2; edge[cnt].l*=edge[cnt].l; cnt++; edge[cnt].u=i; edge[cnt].v=n+2; edge[cnt].l=1ll*min(x-a[i],b[i])*2; edge[cnt].l*=edge[cnt].l; } void add_2(int i,int j){ cnt++; edge[cnt].u=i; edge[cnt].v=j; edge[cnt].l=1ll*(a[i]-a[j])*(a[i]-a[j])+1ll*(b[i]-b[j])*(b[i]-b[j]); } bool comp(const hehe &a,const hehe &b){ return a.l<b.l; } int get(int x){ if(x==f[x]) return x; return f[x]=get(f[x]); } int main(){ cin>>x>>y>>n; for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]); for(int i=1;i<=n;i++){ add_1(i); for(int j=1;j<i;j++) add_2(i,j); } sort(edge+1,edge+1+cnt,comp); for(int i=1;i<=n+2;i++) f[i]=i; for(int i=1;i<=cnt;i++){ int fu=get(edge[i].u); int fv=get(edge[i].v); if(fu==fv) continue; f[fu]=fv; ans=max(ans,edge[i].l); if(get(n+1)==get(n+2)) break; } printf("%.2lf",(double)sqrt(ans)/2); return 0; }
黑暗之魂
分别考虑环上的每一个点
显然我们首先要找到环，考虑用类似拓扑排序的做法，即每次找度数为1的叶子节点不断向上更新，最后环上的点的度数一定为2
f[x]f[x]表示以xx为根的子树中的直径，可以在拓扑排序的过程中处理出
我们已知以环上每一个点为根节点的子树的直径，问题转化成了给出一个环，环上的每一个点有一个点权，点与点之间有边权，设dis[i][j]dis[i][j]为环上两点i,ji,j的距离（最短路径），要计算最大的f[i]+f[j]+dis[i][j]f[i]+f[j]+dis[i][j]
由于只能走最短路径，显然dis[i]][j]dis[i]][j]小于等于环的周长SS的二分之一。我们断环成链，在可行区间范围内维护单调队列。
具体实现是令a[i]a[i]为节点ii的点权，b[i]b[i]为链开头到节点i的路径前缀和，对于每个ii，答案就是a[i]+a[j]+b[i]−b[j](b[i]−b[j]<=S2)a[i]+a[j]+b[i]−b[j](b[i]−b[j]<=S2)取最大值，显然满足决策单调性
#include<algorithm> #include<cstring> #include<cstdio> #include<iostream> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N=1e6+15; int n,tot; ll ans; int head[N],in[N],tmp[N],qq[N]; ll f[N],dis[N],b[N],a[N]; struct EDGE { int to,nxt; ll w; }edge[N<<1]; inline ll read() { char ch=getchar(); ll s=0,f=1; while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) f=-1;ch=getchar();} while (ch>=‘0‘&&ch<=‘9‘) {s=(s<<3)+(s<<1)+ch-‘0‘;ch=getchar();} return s*f; } void add(int u,int v,ll w) { edge[++tot]=(EDGE){v,head[u],w}; head[u]=tot; } void topsort() { queue<int> q; for (int i=1;i<=n;i++) if (in[i]==1) q.push(i); while (!q.empty()) { int k=q.front();q.pop(); for (int i=head[k];i;i=edge[i].nxt) { int y=edge[i].to; if (in[y]==1) continue; ans=max(ans,f[k]+f[y]+edge[i].w); f[y]=max(f[y],f[k]+edge[i].w); if ((--in[y])==1) q.push(y); } } } void dp(int x) { int t=0,y=x,pp; ll len,S=0; do { a[++t]=f[y]; tmp[y]=1; for(pp=head[y];pp;pp=edge[pp].nxt) if(!tmp[edge[pp].to]&&in[edge[pp].to]==2) { y=edge[pp].to; b[t+1]=b[t]+edge[pp].w; break; } }while(pp); if (t==1) return; if (t==2) { for (int i=head[y];i;i=edge[i].nxt) { if (edge[i].to==x) {len=edge[i].w;break;} } ans=max(ans,f[x]+f[y]+len); return; } for (int i=head[y];i;i=edge[i].nxt) { if (edge[i].to==x) { S=b[t]+edge[i].w; b[t+1]=b[t]+edge[i].w; } } for (int i=1;i<t;i++) a[i+t]=a[i],b[t+i]=b[t+1]+b[i]; int l=1,r=1; qq[l]=1; for (int i=2;i<2*t;i++) { while (l<=r&&(b[i]-b[qq[l]]>S/2||i-qq[l]>=t)) l++; if (l<=r) ans=max(ans,b[i]-b[qq[l]]+a[qq[l]]+a[i]); while (l<=r&&a[qq[r]]-b[qq[r]]<=a[i]-b[i]) r--; qq[++r]=i; } } int main() { n=read(); for (int i=1,u,v,w;i<=n;i++) { u=read();v=read();w=read(); in[u]++;in[v]++; if (u==v) continue; add(u,v,w);add(v,u,w); } topsort(); for (int i=1;i<=n;i++) { if (in[i]==2) { dp(i); break; } } printf("%lld\n",ans+1); return 0; }
传送门
很明显这是道树形dp。
如果没有传送门的话，树上的距离之和就是边权之和的2倍，但是可以用传送省掉某些边，所以开数组dp[i][1/0]表示在i号结点放/不放传送门能省掉的最大权值。
通过分析可得，对于以任意一个结点为根的子树，如果把传送门放在这个结点上的话，那么与ta相连的每个点都可以直接传送会来，所以dp[u][1]+=max(dp[v][0]+edge[i].val,dp[v][1])。
如果不放的话，就只能把与这个结点的相连的最长子链给省掉，并且那条子链也不能放传送门（不然回不去了），
所以dp[u][0]=max(dp[u][0],dp[v][0]+edge[i].val)。
#include<bits/stdc++.h> #define maxn 1000010 #define ll long long using namespace std; int n,head[maxn],k; ll sum,dp[maxn][2]; struct node { int to,nxt; ll val; } edge[maxn*2]; void add(int u,int v,ll w) { edge[++k].nxt=head[u]; edge[k].to=v; edge[k].val=w; head[u]=k; } void dfs(int u,int fa) { for(int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to; if(v==fa) continue ; dfs(v,u); dp[u][1]+=max(dp[v][0]+edge[i].val,dp[v][1]); dp[u][0]=max(dp[u][0],dp[v][0]+edge[i].val); } } int main() { scanf("%d",&n); int x,y; ll z; for(int i=1;i<n;i++) { scanf("%d%d%lld",&x,&y,&z); add(x,y,z),add(y,x,z); sum+=z*2; } dfs(1,1); printf("%lld\n",sum-max(dp[1][0],dp[1][1])); return 0; }
原文：https://www.cnblogs.com/Heartbeat358/p/12391503.html