社区讨论

13分并没有看出什么错,求巨神帮看

P3128[USACO15DEC] Max Flow P参与者 3已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@mi6xrwvl
此快照首次捕获于
2025/11/20 12:33
4 个月前
此快照最后确认于
2025/11/20 12:33
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#define MAXN 50000+10
#define MAXM 50
using namespace std;
inline int read(){
    int out=0;
    char c=getchar();
    while(c<48||c>57) c=getchar();
    while(c<=57&&c>=48){
        out=(out<<1)+(out<<3)+c-48;
        c=getchar();
    }
    return out;
}
inline void write(int x){
    if(x>9) write(x/10);
    putchar(x%10+48);
}
vector<int>edge[MAXN];
int deep[MAXN],cf[MAXN],sum[MAXN];
int fa[MAXN][MAXM];
int n,m,maxh,ans=0;
bool vis[MAXN];
void bfs(){
    queue<int>q;
    memset(vis,0,sizeof(vis));
    memset(deep,0,sizeof(deep));
    memset(fa,0,sizeof(fa));
    q.push(1);
    vis[1]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<edge[u].size();++i){
            int v=edge[u][i];
            if(!vis[v]){
                vis[v]=1;
                q.push(v);
                fa[v][0]=u;
                deep[v]=deep[u]+1;
            }
        }
    }
}
void init(){
    n=read();
    m=read();
    for(int i=1;i<n;++i){
        int u=read();
        int v=read();
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    bfs();
    maxh=log(n)/log(2);
    for(int j=1;j<=maxh;++j)
        for(int i=1;i<=n;++i)
            fa[i][j]=fa[fa[i][j-1]][j-1];
}
int lca(int u,int v){
    if(deep[u]<deep[v]) swap(u,v);
    int d=deep[u]-deep[v];
    for(int i=0;i<=maxh;++i) if((d>>i)&1) u=fa[u][i];
    if(u==v) return u;
    for(int i=maxh;i>=0;--i){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[u][i];
        }
    }
    return fa[u][0];
}
inline void dfs(int u){
    for(int i=0;i<edge[u].size();++i){
        int v=edge[u][i];
        if(v==fa[u][0]) continue;
        dfs(v);
        cf[u]+=cf[v];
    }
    ans=max(ans,cf[u]);
}
int main(){
    init();
    for(int i=1;i<=m;++i){
        int u=read();
        int v=read();
        int r=lca(u,v);
        ++cf[u];
        ++cf[v];
        --cf[r];
        --cf[fa[r][0]];
    }
    dfs(1);
    write(ans);
    putchar(10);
    return 0;
}

回复

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

正在加载回复...