社区讨论
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 条回复,欢迎继续交流。
正在加载回复...