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