社区讨论
存个打到一大半的程序
灌水区参与者 10已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @mi6hq7e4
- 此快照首次捕获于
- 2025/11/20 05:04 4 个月前
- 此快照最后确认于
- 2025/11/20 05:04 4 个月前
CPP
#include<cstdio>
#include<cmath>
#include<vector>
#define MAXN 300001
using namespace std;
struct Edge
{
int to,w;
Edge(){}
Edge(int a,int b)
{
to=a;w=b;
}
};
struct Way
{
int from,to,len;
}way[MAXN];
struct data
{
int left,right,vmin,addv;
}tree[4*MAXN];
vector <Edge> E[MAXN];
int dis[MAXN],deep[MAXN],m,n,g[MAXN][20],power,root,tree_c1[MAXN];
int maxway=1,visit[MAXN],re[MAXN],arr[MAXN],totw,T;
int min(int a,int b){if (a>b)return b;else return a;}
int max(int a,int b){if (a>b)return a;else return b;}
void read(int & x)
{
char c=getchar();x=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
}
int build(int x)
{
int i;
for(i=1;i<=power;i++)
{
g[x][i]=g[g[x][i-1]][i-1];
if (g[x][i]==0) break;
}
int len=E[x].size();
for(i=0;i<len;i++)
{
Edge e=E[x][i];
if (e.to!=g[x][0])
{
g[e.to][0]=x;
deep[e.to]=deep[x]+1;
dis[e.to]=dis[x]+e.w;
build(e.to);
}
}
return 0;
}
int LCA(int x,int y)
{
int i;
if (deep[x]>deep[y]) {int t;t=x;x=y;y=t;}
for(i=power;i>=0;i--)
if (deep[g[y][i]]>=deep[x]) y=g[y][i];
for(i=power;i>=0;i--)
if(g[x][i]!=g[y][i]) {x=g[x][i];y=g[y][i];}
if (x!=y) x=g[x][0];
return x;
}
int dfs_1(int x,int tot)
{
if (x==way[maxway].to) {totw=tot-1;tree_c1[x]=way[maxway].from;return 1;}
int len=E[x].size();
for(int i=0;i<len;i++)
if(visit[E[x][i].to]==0)
{
visit[E[x][i].to]=1;
if (dfs_1(E[x][i].to,tot+1)) {re[tot]=x;visit[E[x][i].to]=0;tree_c1[x]=way[maxway].from;return 1;}
visit[E[x][i].to]=0;
}
return 0;
}
int dfs_2(int x,int color)
{
int len=E[x].size();
for(int i=0;i<len;i++)
if (tree_c1[E[x][i].to]==0) {tree_c1[E[x][i].to]=color;dfs_2(E[x][i].to,color);}
return 0;
}
void buildtree(int x,int left,int right)
{
tree[x].left=left;tree[x].right=right;
if (left==right) {tree[x].vmin=arr[left];return;}
int mid=(left+right)>>1;
buildtree(x<<1,left,mid);
buildtree(x<<1|1,mid+1,left);
tree[x].vmin=min(tree[x<<1].vmin,tree[x<<1|1].vmin);
return;
}
int main()
{
int i,x,y,z;
read(n);read(m);
root=1;
power=floor(log(n+0.0)/log(2.0));
for(i=1;i<n;i++)
{
read(x);read(y);read(z);
E[x].push_back(Edge(y,z));
E[y].push_back(Edge(x,z));
}
deep[root]=1;
deep[0]=-1;
dis[root]=0;
build(root);
for(i=1;i<=m;i++)
{
read(x);read(y);
way[i].from=x;way[i].to=y;
way[i].len=dis[x]+dis[y]-2*dis[LCA(x,y)];
if (way[i].len>way[maxway].len) maxway=i;
}
visit[way[maxway].from]=1;
tree_c1[way[maxway].from]=way[maxway].from;
dfs_1(way[maxway].from,1);
visit[way[maxway].from]=0;
for(int i=1;i<=n;i++)
if (tree_c1[i]==way[maxway].from) dfs_2(i,i);
for(int i=1;i<=totw;i++)
arr[i]=way[maxway].len-re[i];
buildtree(1,1,totw);
for(int i=1;i<=m;i++)
if (i!=maxway&&tree_c1[way[i].from]!=tree_c1[way[i].to])
{
int x=tree_c1[way[i].from],y=tree_c1[way[i].to],t;
if (x>y) {t=x;x=y;y=t;}
y--;
update(1,x,y,)
}
return 0;
}
回复
共 9 条回复,欢迎继续交流。
正在加载回复...