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