社区讨论

莫名WA掉,求助dalao

P3119[USACO15JAN] Grass Cownoisseur G参与者 2已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@mi6z0mfr
此快照首次捕获于
2025/11/20 13:08
4 个月前
此快照最后确认于
2025/11/20 13:08
4 个月前
查看原帖
这个题要维护两个dis,而且由于是DAG,感觉赋初值(也就是1点所处联通快大小)与否没有影响,无非是最后的加减变了而已,可是不赋初值交就会WA4个点,赋初值就会WA掉,求dalao们帮助,当然,也有可能是我代码的锅emmm
WA掉的代码:
CPP
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rint register int
using namespace std;
const int mx=100005;
int n,m,cnt,tot,t,ans;
int num[mx],vis[mx],tm[mx],bel[mx],sz[mx],dfn[mx],low[mx],dis1[mx],dis2[mx],num1[mx],num2[mx];
struct node{
    int next,y,x;
};
node road[mx],r1[mx],r2[mx];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
inline void add(int u,int v)
{
    road[++cnt].x=u;road[cnt].y=v;road[cnt].next=num[u];num[u]=cnt;
}
void dfs(int u)
{
    int v;tm[++cnt]=u;dfn[u]=low[u]=++tot;vis[u]=1;
    for(rint i=num[u];i;i=road[i].next){
        v=road[i].y;if(!vis[v]) dfs(v);
        if(vis[v]!=2) low[u]=min(low[u],low[v]);
    }
    if(low[u]==dfn[u]){
        v=0;++t;
        while(v!=u){
            v=tm[cnt--];vis[v]=2;bel[v]=t;++sz[t];//printf("v=%d\n",v);
        }
    }
}
inline void tarjan()
{
    cnt=0;
    for(rint i=1;i<=n;++i) if(vis[i]!=2) dfs(i);
}
inline void rebuild()
{
    int u,v;cnt=0;
    for(rint i=1;i<=m;++i){
        u=road[i].x;v=road[i].y;u=bel[u];v=bel[v];
        if(u!=v){
            r1[++cnt].next=num1[u];num1[u]=cnt;r1[cnt].y=v;
            r2[cnt].next=num2[v];num2[v]=cnt;r2[cnt].y=u;
        }
    }
}
inline void spfa()
{
    int head=0,tail=1,u,v;tm[1]=bel[1];
    while(head<tail){
        u=tm[++head];
        for(rint i=num1[u];i;i=r1[i].next){
            v=r1[i].y;
            if(dis1[v]<dis1[u]+sz[v]){
                dis1[v]=dis1[u]+sz[v];
                tm[++tail]=v;
            }
        }
    }
    head=0,tail=1;tm[1]=bel[1];
    while(head<tail){
        u=tm[++head];
        for(rint i=num2[u];i;i=r2[i].next){
            v=r2[i].y;
            if(dis2[v]<dis2[u]+sz[v]){
                dis2[v]=dis2[u]+sz[v];
                tm[++tail]=v;
            }
        }
    }
}
int main()
{
    n=read();m=read();int u,v;
    for(rint i=1;i<=m;++i) u=read(),v=read(),add(u,v);
    tarjan();rebuild();spfa();//for(int i=1;i<=n;++i) printf("bel[%d]=%d   sz_bel=%d\n",i,bel[i],sz[bel[i]]);
    for(int i=1;i<=cnt;++i){
        u=r1[i].y;v=r2[i].y;
        if(dis1[u]&&dis2[v]) if(dis1[u]+dis2[v]>ans) ans=dis1[u]+dis2[v];
        if(!dis1[u]&&u==1&&dis2[v]) if(dis1[u]>ans) if(dis1[u]+dis2[v]>ans) ans=dis1[u]+dis2[v];
        if(dis1[v]&&dis2[u]) if(dis1[v]+dis2[u]>ans) ans=dis1[v]+dis2[u];
        if(dis1[u]&&!dis2[v]&&v==1) if(dis1[v]+dis2[u]>ans) ans=dis1[v]+dis2[u];
    }//printf("ans=%d\n",ans);
    if(!ans) if(sz[bel[1]]!=n) ans=1;
    printf("%d",ans+sz[bel[1]]);
    return 0;
}

回复

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

正在加载回复...