社区讨论

13分然而并不能看出有什么问题 求大佬解救

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

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@mi6wxa9f
此快照首次捕获于
2025/11/20 12:09
4 个月前
此快照最后确认于
2025/11/20 12:09
4 个月前
查看原帖
CPP
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define MAXN 50007
using namespace std;
int n, k, head[MAXN], num_edge, vis_time[MAXN];
int son[MAXN], father[MAXN], dep[MAXN], size[MAXN], top[MAXN];
struct add
{
    int to, next;
}edge[MAXN<<1];
void add_edge(int from, int to)
{
    edge[++num_edge].to = to;
    edge[num_edge].next = head[from];
    head[from] = num_edge;
}
int read()
{
    int tt = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c))
    {
        tt = (tt<<1)+(tt<<3)+(c&15);
        c = getchar();
    }
    return tt;
}
void dfs1(int u, int fa)
{
    father[u] = fa;
    size[u] = 1;
    dep[u] = dep[fa]+1;
    for(int i=head[u]; i; i=edge[i].next)
    {
        int v = edge[i].to;
        if(v == fa) continue;
        dfs1(v, u);
        size[u] += size[v];
        if(size[v] > size[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int topu)
{
    top[u] = topu;
    if(!son[u]) return;
    for(int i=head[u]; i; i=edge[i].next)
    {
        int v = edge[i].to;
        if(v == father[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
void dfs3(int u)
{
    for(int i=head[u]; i; i=edge[i].next)
    {
        int v = edge[i].to;
        if(v == father[u]) continue;
        dfs3(v);
        vis_time[u] += vis_time[v];
    }
}
int LCA(int x, int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = father[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
int main()
{
    n = read(), k = read();
    for(int i=1; i<=n-1; ++i)
    {
        int x = read(), y = read();
        add_edge(x, y); add_edge(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for(int i=1; i<=k; ++i)
    {
        int start = read(), finish = read();
        int lca = LCA(start, finish);
        vis_time[start]++; vis_time[finish]++;
        vis_time[lca]--; vis_time[father[lca]]--;
    }
    dfs3(1);
    int maxx = 0;
    for(int i=1; i<=n; ++i) maxx = max(maxx, vis_time[i]);
    printf("%d\n", maxx);
    return 0;	
}
莫名其妙挂掉了
第一个点比标准输出少了一万多
求大佬解救

回复

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

正在加载回复...