社区讨论

13个点MLE什么情况?蒟蒻求助各位神犇

P2680[NOIP 2015 提高组] 运输计划参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi6i3ftg
此快照首次捕获于
2025/11/20 05:14
4 个月前
此快照最后确认于
2025/11/20 05:14
4 个月前
查看原帖
CPP
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 300010
using namespace std;
int n,m,i,l,r;
struct node1{
    int v,len;
};
struct node2{
    int v,id;
};
vector <node1> pic[N];
vector <node2> edge[N];
int d[1000005],op[1000005],u[1000005],v[1000005],f[1000005],vis[1000005],dis[10000005];
int ans[1000005],lca[1000005];
int find(int x){
    if (f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
void tarjan(int u){
    vis[u]=1;
    int i;
    for (i=0;i<pic[u].size();i++){
        int V=pic[u][i].v,Len=pic[u][i].len;
        if (!vis[V]){
            dis[V]=dis[u]+Len;
            tarjan(V);
            if (find(V)!=find(u)) f[find(V)]=find(u);
        }
    }
    for (i=0;i<edge[u].size();i++){
        int V=edge[u][i].v,Id=edge[u][i].id;
        if (vis[V]){
            ans[Id]=dis[V]+dis[u]-2*dis[find(V)];
            if (ans[Id]>r) r=ans[Id];
            lca[Id]=find(V);
        }
    }
}
void dfs(int u)
{
    vis[u]=1;
    for (int i=0;i<pic[u].size();i++)
    {
        int V=pic[u][i].v,Len=pic[u][i].len;
        if (!vis[V])
        {
            op[V]=Len;
            dfs(V);
            d[u]+=d[V];
        }
    }
}
bool solve(int mid){
    memset(d,0,sizeof(d));
    memset(vis,0,sizeof(vis));
    int k=0;
    for (int i=1;i<=m;i++) if (ans[i]>mid){
        k++;
        d[u[i]]++;d[v[i]]++;d[lca[i]]-=2;
    }
    dfs(1);
    int maxx=0;
    for (int i=1; i<=n; i++) 
        if (d[i]==k) maxx=max(maxx,op[i]);
    for (int i=1; i<=m; i++) 
        if (ans[i]>mid && ans[i]-maxx>mid)  return 0;
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for (i=1;i<n;i++){
        int u,v,l;
        scanf("%d%d%d",&u,&v,&l);
        pic[u].push_back((node1){v,l});
        pic[v].push_back((node1){u,l});
    }
    for (int i=1; i<=n; i++)
        f[i]=i;
    for (int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        edge[u[i]].push_back((node2){v[i],i});
        edge[v[i]].push_back((node2){u[i],i});
    }
    tarjan(1);
    l=0;
    while (l<r){
        int mid=(l+r)>>1;
        if (solve(mid)) r=mid; else l=mid+1;
    }
    printf("%d\n",r);
}

回复

6 条回复,欢迎继续交流。

正在加载回复...