社区讨论

存个打到一大半的程序

灌水区参与者 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 条回复,欢迎继续交流。

正在加载回复...