社区讨论

为什么一开始数组开小了就会报TLE

P3128[USACO15DEC] Max Flow P参与者 4已保存回复 9

讨论操作

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

当前回复
9 条
当前快照
1 份
快照标识符
@mi6m44b2
此快照首次捕获于
2025/11/20 07:07
4 个月前
此快照最后确认于
2025/11/20 07:07
4 个月前
查看原帖
CPP
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=50000+10;
const int maxk=100000+10;
int n,k,beg[maxn],len,x[maxk],y[maxk],ans;
int maxdep,dep[maxn],Log[maxn],lca[maxn],a[maxn][20];
int sum[maxn];
bool vis[maxn];
int _max(int x,int y){
    return x>y ? x:y;
}
struct edge{
    int to;
    int last;
}E[maxn*2];
void add(int u,int v){
    len++;
    E[len].to=v;
    E[len].last=beg[u];
    beg[u]=len;
}
void dfs(int u,int deep){
    vis[u]=1;
    dep[u]=deep;
    maxdep=_max(maxdep,deep);
    for(int i=beg[u];i;i=E[i].last){
        int v=E[i].to;
        if(vis[v])continue;
        a[v][0]=u;
        dfs(v,deep+1);
    }
}
int query(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    while(dep[u]>dep[v])u=a[u][Log[dep[u]-dep[v]]];
    int k=0;
    while(a[u][k+1]!=a[v][k+1])k++;
    while(u!=v){
        u=a[u][k];v=a[v][k];
        while(a[u][k]==a[v][k] && k!=0)k--;
    }
    return u;
}
void handle(){
    for(int i=1;(1<<i)<=maxdep;i++)
        for(int j=1;j<=n;j++)
            if(dep[j]-(1<<i)>0)
                a[j][i]=a[a[j][i-1]][i-1];
    for(int i=1;i<=k;i++){
        lca[i]=query(x[i],y[i]);
        sum[x[i]]++;sum[y[i]]++;
        sum[a[lca[i]][0]]--;
        sum[lca[i]]--;
    }
}
void solve(int u){
    vis[u]=1;
    for(int i=beg[u];i;i=E[i].last){
        int v=E[i].to;
        if(vis[v])continue;
        solve(v);
        sum[u]+=sum[v];
    }
}
int main(){
#ifndef ONLINE_JUDGE
    //freopen("max_flow.in","r",stdin);
    //freopen("max_flow.out","w",stdout);
#endif
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    for(int i=1;i<=k;i++)
        scanf("%d%d",&x[i],&y[i]);
    dfs(1,1);
    for(int i=0;i<=maxdep;i++)
        Log[i]=floor(log(i)/log(2));
    handle();
    memset(vis,0,sizeof(vis));
    solve(1);
    for(int i=1;i<=n;i++)
        ans=_max(ans,sum[i]);
    printf("%d\n",ans);
    return 0;
}

回复

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

正在加载回复...