[蒟蒻在线求解]一个很神奇的不知道与数据有没有关系的问题

回复帖子

@Drifterming 2018-12-26 10:44 回复

FgR7xU.md.png

RT,左边的代码是我从博客里粘的Candy?大佬的,她本来建的是dfs树,我给她改成了并查集建树(我也不知道是不是这样说),但是仍然可以AC。但是我发现当两端点是21和67的时候,到最后他们间边的编号神奇地变了... 而且也没有发生hash碰撞。 FgWmJP.png

FgWpRK.png

我用的map,最后边的编号没有变,但是一直WA...感觉很神奇,有没有大佬可以解答一下?

这是Candy?的原博客

@Drifterming 2018-12-26 10:46 回复 举报

这是我将她的代码改成了并查集,可能调试的很乱

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+5, M=1e5+5, P=1999997;
#define lc x<<1
#define rc x<<1|1
#define mid ((l+r)>>1)
#define lson lc, l, mid
#define rson rc, mid+1, r
typedef long long ll;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int n, m, trn, mark[N], Q, c, x, y, del[M];
int Hash[P];
inline int& Map(int x) {return Hash[x%P];}
struct meow{int u, v;} a[M], tr[N];
struct qmeow{int c, u, v, qid;}q[M];
int ans[M];

struct Graph{
    struct edge{int v, ne, id;} e[M<<1];
    int cnt, h[N];
    inline void ins(int u, int v, int id) {
        e[++cnt]=(edge){v, h[u], id}; h[u]=cnt;
        e[++cnt]=(edge){u, h[v], id}; h[v]=cnt;
    }
    int vis[N];
    void dfs(int u) {
        vis[u]=1;
        for(int i=h[u];i;i=e[i].ne)
            if(!vis[e[i].v]) {
                mark[e[i].id]=1;
                tr[++trn]=a[e[i].id];
                dfs(e[i].v);
            }
    }
}G;

struct edge{int v, ne;} e[N<<1];
int cnt, h[N];
inline void ins(int u, int v) {
    e[++cnt]=(edge){v, h[u]}; h[u]=cnt;
    e[++cnt]=(edge){u, h[v]}; h[v]=cnt;
}
int dfn[N], dfc, fa[N], top[N], deep[N], mx[N], size[N];
void dfs(int u) {
    size[u]=1;
    for(int i=h[u];i;i=e[i].ne) {
        int v=e[i].v;
        if(v==fa[u]) continue;
        deep[v]=deep[u]+1; fa[v]=u;
        dfs(v);
        size[u]+=size[v];
        if(size[v]>size[mx[u]]) mx[u]=v;
    }
}
void dfs2(int u, int anc) { //printf("u anc %d %d\n",u,anc);
    dfn[u] = ++dfc; top[u] = anc;
    if(mx[u]) dfs2(mx[u], anc);
    for(int i=h[u];i;i=e[i].ne) 
        if(e[i].v != fa[u] && e[i].v != mx[u]) dfs2(e[i].v, e[i].v);
}

struct SegmentTree{
    struct meow{
        int sum, tag;
        meow():tag(-1){}
    }t[N<<2];
    inline void paint(int x, int l, int r, int v) {
//      cout<<x<<' '<<l<<' '<<r<<' '<<v<<'\n';
        t[x].tag = v;
        t[x].sum = (r-l+1)*v;
    }
    inline void pushDown(int x, int l, int r) {
        if(t[x].tag != -1) {
            paint(lson, t[x].tag);
            paint(rson, t[x].tag);
            t[x].tag = 0;
        }
    }
    void build(int x, int l, int r) {
        if(l==r) t[x].sum=1;
        else {
            build(lson); build(rson);
            t[x].sum = t[lc].sum + t[rc].sum;
        }
    }
    inline void cover(int x, int l, int r, int ql, int qr, int v) {
        if(ql<=l && r<=qr) paint(x, l, r, v);
        else {
            pushDown(x, l, r);
            if(ql<=mid) cover(lson, ql, qr, v);
            if(mid<qr)  cover(rson, ql, qr, v);
            t[x].sum = t[lc].sum + t[rc].sum;
        }
    }
    inline int que(int x, int l, int r, int ql, int qr) {
        if(ql<=l && r<=qr) return t[x].sum;
        else {
            pushDown(x, l, r);
            int ans=0;
            if(ql<=mid) ans+=que(lson, ql, qr);
            if(mid<qr)  ans+=que(rson, ql, qr);
            return ans;
        }
    }

    int zz()
    {
        cout<<t[1].sum<<'\n';
    }
}S;

void cover(int x, int y, int v) {
    while(top[x] != top[y]) {
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        S.cover(1,1,n,dfn[top[x]],dfn[x],v);
        x = fa[top[x]];
    }
    if(dfn[x] > dfn[y]) swap(x, y);
    if(x!=y) S.cover(1,1,n,dfn[x]+1,dfn[y],v);
}
int query(int x, int y) {
    int ans=0;
    while(top[x] != top[y]) {
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        ans += S.que(1,1,n,dfn[top[x]],dfn[x]);
        x = fa[top[x]];
    }
    if(dfn[x] > dfn[y]) swap(x, y);
    if(x!=y) ans += S.que(1,1,n,dfn[x]+1,dfn[y]);
    return ans;
}

int F[123456];
int find(int x)
{
    return x==F[x]?x:F[x]=find(F[x]);
}
int main() {
freopen("6.in","r",stdin);
//  freopen("466.out","w",stdout);
    n=read(); m=read();
    int T=21*n+67;
    for(int i=1;i<=n;++i) F[i]=i;
    for(int i=1; i<=m; i++) {
        x=read(); y=read(); if(x>y) swap(x, y);
        a[i]=(meow){x, y}; 
        Map(x*n+y)=i;
//        if(x==21&&y==67)
        if(x*n+y==T)
            cout<<x<<' '<<y<<' '<<Map(T)<<'\n';
    }
    cout<<Map(T)<<'\n';
    int A=0;
    while(true) {
        c=read();
        if(c==-1) break;
        x=read(); y=read(); if(x>y) swap(x, y);
        q[++Q]=(qmeow){c, x, y, 0};
        if(c==0)del[ Map(x*n+y) ] = 1/*,cout<<x<<' '<<y<<' ',cout<<Map(x*n+y)<<'\n'*/;
        else q[Q].qid = ++ans[0];
    }
    int kk=0;
    for(int i=1; i<=m; i++)
    {
        if(del[i]) continue;
        int q=find(a[i].u),p=find(a[i].v);
        if(q==p) continue;
        F[q]=p;mark[i]=1;
        ins(a[i].u,a[i].v);++kk;
//      G.ins(a[i].u, a[i].v, i); //printf("hi %d\n",i);
    }
//  cout<<kk<<'\n';
//  G.dfs(1);
//    cout<<A<<'\n';
//    cout<<trn<<'\n';
//    for(int i=1; i<=trn; i++) ins(tr[i].u, tr[i].v);// printf("tr %d %d\n",tr[i].u, tr[i].v);
    dfs(1); dfs2(1, 1);
    S.build(1, 1, n);
    /*S.zz();*/int k=0;
    for(int i=1; i<=m; i++)
        if(!mark[i] && !del[i])
        {
//          cout<<i<<'\n';
            cover(a[i].u, a[i].v, 0);
            ++k;
//          cout<<a[i].u<<' '<<a[i].v<<'\n';
//          cout<<a[i].u<<' '<<a[i].v<<'\n';
        }
//  cout<<k<<'\n';
//  S.zz();
    for(int i=Q; i>=1; i--) { //printf("Q %d\n",i);
        if(q[i].c==0) cover(q[i].u, q[i].v, 0);
        else ans[q[i].qid] = query(q[i].u, q[i].v);
    }
//    for(int i=1; i<=ans[0]; i++) printf("%d\n",ans[i]);
}
@Drifterming 2018-12-26 10:47 回复 举报

这是我用的stl的map

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;

typedef long long LL;

inline int read()
{
    char c=getchar();int num=0,f=1;
    for(;!isdigit(c);c=getchar())
        f=c=='-'?-1:f;
    for(;isdigit(c);c=getchar())
        num=num*10+c-'0';
    return num*f;
}

const int N=1e5+5;

int n,m,C;

map<pii,int> ma;
bool cut[N];
int A[N],B[N];

int head[N],num_edge;
struct Edge
{
    int v,nxt;
}edge[N<<1];

inline void add_edge(int u,int v)
{
    edge[++num_edge].v=v;
    edge[num_edge].nxt=head[u];
    head[u]=num_edge;
}

struct OPT
{
    int typ,a,b;
}opt[N];

int fa[N];
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

struct NODE
{
    int s,t,siz,dep;
    int top,son,fa;
}node[N];

void dfs1(int u,int fa)
{
    node[u].siz=1;
    for(int i=head[u],v;i;i=edge[i].nxt)
    {
        v=edge[i].v;
        if(v==fa) continue;
        node[v].fa=u,node[v].dep=node[u].dep+1;
        dfs1(v,u);
        node[u].siz+=node[v].siz;
        if(node[v].siz>node[node[u].son].siz)
            node[u].son=v;
    }
}

int bound;
void dfs2(int u,int top)
{
    node[u].s=++bound;node[u].top=top;
    if(node[u].son)
    {
        dfs2(node[u].son,top);
        for(int i=head[u],v;i;i=edge[i].nxt)
        {
            v=edge[i].v;
            if(v==node[u].fa||v==node[u].son)
                continue;
            dfs2(v,v);
        }
    }
    node[u].t=bound;
}

#define Root tree[root]
#define lson tree[root].ls
#define rson tree[root].rs
#define Lson tree[lson]
#define Rson tree[rson]
struct Tree
{
    int ls,rs,sum,tag;
}tree[N*2];
int Rt,now_node;

void build(int &root,int l,int r)
{
    root=++now_node;Root.sum=r-l+1;
    if(l==r)
        return;
    int mid=(l+r)>>1;
    build(lson,l,mid),build(rson,mid+1,r);
}

void pushdown(int root)
{
    Lson.tag=Rson.tag=1;
    Lson.sum=Rson.sum=0;
    Rson.tag=0;
}

void modify(int root,int l,int r,int L,int R)
{
    if(l==L&&r==R){Root.sum=0,Root.tag=1;return;}
    if(Root.tag) pushdown(root);
    int mid=(l+r)>>1;
    if(R<=mid) modify(lson,l,mid,L,R);
    else if(L>mid) modify(rson,mid+1,r,L,R);
    else modify(lson,l,mid,L,mid),modify(rson,mid+1,r,mid+1,R);
    Root.sum=Lson.sum+Rson.sum;
}

int query(int root,int l,int r,int L,int R)
{
    if(l==L&&r==R) return Root.sum;
    if(Root.tag) pushdown(root);
    int mid=(l+r)>>1;
    if(R<=mid) return query(lson,l,mid,L,R);
    else if(L>mid) return query(rson,mid+1,r,L,R);
    else return query(lson,l,mid,L,mid)+query(rson,mid+1,r,mid+1,R);
}

void Modify(int x,int y)
{
    int fx=node[x].top,fy=node[y].top;
    while(fx!=fy)
    {
        if(node[fx].dep<node[fy].dep)
            swap(x,y),swap(fx,fy);
        modify(1,1,n,node[fx].s,node[x].s);
        x=node[fx].fa,fx=node[x].top;
    }
    if(x==y) return;
    if(node[x].dep>node[y].dep) swap(x,y);
    modify(1,1,n,node[x].s+1,node[y].s);
}

int Query(int x,int y)
{
    int res=0,fx=node[x].top,fy=node[y].top;
    while(fx!=fy)
    {
        if(node[fx].dep<node[fy].dep)
            swap(x,y),swap(fx,fy);
        res+=query(1,1,n,node[fx].s,node[x].s);
        x=node[fx].fa,fx=node[x].top;
    }
    if(x==y) return res;
    if(node[x].dep>node[y].dep) swap(x,y);
    return res+query(1,1,n,node[x].s+1,node[y].s);
}

int Ans[N],ans;
int main()
{
    freopen("6.in","r",stdin);
//  freopen("233.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        fa[i]=i;
    for(int i=1;i<=m;++i)
    {
        A[i]=read(),B[i]=read();
        if(A[i]>B[i]) swap(A[i],B[i]);
        if(A[i]==21&&B[i]==67)
            cout<<i<<'\n';
        ma[mp(A[i],B[i])]=i;
    }
    cout<<ma[mp(21,67)]<<'\n';
    for(int a;;)
    {
        a=read();if(a==-1) break;
        opt[++C].typ=a,opt[C].a=read(),opt[C].b=read();
        if(opt[C].a>opt[C].b) swap(opt[C].a,opt[C].b);
        if(opt[C].typ==0)   //破坏边 
        {
//          cout<<opt[C].a<<' '<<opt[C].b<<' ';
//          cout<<ma[mp(opt[C].a,opt[C].b)]<<'\n';
            cut[ma[mp(opt[C].a,opt[C].b)]]=1;
        }
    }
    int zz=0;
    for(int i=1,u,v;i<=m;++i)   //造棵生成树 
    {
        if(cut[i]) continue;        //被破坏了 
        u=find(A[i]),v=find(B[i]);
        if(u!=v)    //还没联通,连起来 
        {
            add_edge(A[i],B[i]),add_edge(B[i],A[i]);
            fa[u]=v;cut[i]=1;
        }
    }
    dfs1(1,1),dfs2(1,1);
    build(Rt,1,n);
//  cout<<tree[1].sum<<'\n';
    for(int i=1;i<=m;++i)       //消除非树边的影响 
    {
        if(cut[i]) continue;
        Modify(A[i],B[i]);
        ++zz;
//      cout<<i<<'\n';
//      cout<<A[i]<<' '<<B[i]<<'\n';
    }
//  cout<<zz<<'\n';
//  cout<<no<<'\n'<<tmp<<'\n';
//  cout<<tree[1].sum<<'\n';
    for(int i=C;i;--i)
    {
        if(opt[i].typ==0)
            Modify(opt[i].a,opt[i].b);
        else
            Ans[++ans]=Query(opt[i].a,opt[i].b);
    }
//  for(int i=ans;i;--i)
//      cout<<Ans[i]<<'\n';
    return 0;
}

如果有哪位大佬能解答,蒟蒻不胜感激,改了一上午了qwq。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。