ZJT's Blog

大変に気分がいい~

集训队作业之AGC017-E

2017-12-16 14:12017-12-16 14:1
集训队作业AtCoder欧拉回路

传送门

先建出一个图模型,把每个点拆成左右两个点,左边代表落在地上,右边代表悬空。然后问题就转化成给一些边,能不能找出若干条从右边到左边的路径,使得覆盖每条边恰好一次。

我们可以把这个问题转化成加若干条左边到右边的边,使得每个连通块都存在欧拉回路。记每个点的入度减出度为$d_i$。如果左边有$d_i<0$的点,或者右边有$d_i>0$的点,则显然不合法,可以直接判掉。

否则,我们把现有的连通块缩点(可以无视边的方向,因为如果最后能使得所有点出度等于入度,则基图的所有连通块一定都强联通),处理出每个连通块可以连出的边以及连入的边。可以证明,只要不存在孤立的连通块(既没有连出的边也没有连入的边),以及可以连的边数大于等于$($连通块数$-1)$,就一定有解。所以直接用并查集维护每个连通块就行啦。

#include <cstdio>
#include <cstring>
#define MAXN 1000010

int n,h;
int g[MAXN],nume;
int p[MAXN][2],nump;
int d[MAXN],size[MAXN],sd[MAXN][2];
bool tag[MAXN];
int f[MAXN];

int getf(int x){
    if(f[x]==x) return x;
    return f[x]=getf(f[x]);
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    for(int i=1;i<MAXN;i++) f[i]=i;
    memset(g,-1,sizeof g);
    scanf("%d%d",&n,&h);
    for(int i=1;i<=h;i++) p[i][0]=++nump;
    for(int i=1;i<=h;i++) p[i][1]=++nump;
    for(int i=1;i<=n;i++){
        int t1,t2,t3,t4,u,v;
        scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
        if(!t3) u=p[t1][1];
        else u=p[t3][0];
        if(!t4) v=p[t2][0];
        else v=p[t4][1];
        if(getf(u)^getf(v)) f[f[u]]=f[v];
        d[u]--;
        d[v]++;
        tag[u]=tag[v]=1;
    }
    for(int i=1;i<=n;i++) 
        if(d[p[i][0]]<0 || d[p[i][1]]>0){
            puts("NO");
            return 0;
        }
    for(int i=1;i<=nump;i++){
        size[getf(i)]++;
        if(d[i]<0) sd[getf(i)][0]+=-d[i];
        else sd[getf(i)][1]+=d[i];
        if(tag[i]) tag[getf(i)]=1;
    }
    int numc=0;
    int s0=0,s1=0;
    for(int i=1;i<=nump;i++)
        if(getf(i)==i && tag[i]){
            if(!sd[i][0] && !sd[i][1]){
                puts("NO");
                return 0;
            }
            s0+=sd[i][0];
            s1+=sd[i][1];
            numc++;
        }
    if(s0^s1){
        puts("NO");
        return 0;
    }
    if(s0<numc-1){
        puts("NO");
        return 0;
    }
    puts("YES");
    return 0;
}

查看详细内容

集训队作业之AGC016-D

2017-9-24 2:72017-9-24 2:7
AtCoder欧拉回路集训队作业

集训队作业发布啦,再颓就要GG啦!

先把自己负责的两道题做了吧。


传送门

考虑每次操作后,新的异或和就是这次操作中被替换掉的那个数。那这道题其实就是不断地拿一个数到处瞎替换,直到匹配上为止。

然后看起来就比较像欧拉回路了?我们直接把每个数看作一个点,然后把每个位置的替换看作一条边。这样的话,走$(u,v)$这条边就意味这通过替换某个位置,把当前异或和从$u$变成了$v$。这样的话,只要从最初的异或和开始,走一个欧拉回路就行了。

然而不存在欧拉回路的时候怎么办呢?如果有两个环彼此不相连,那么显然是不能从某个点出发走完这两个环的。这时候我们再考虑回边$(u,v)$的意义,其实就是这个位置本来是$v$,用$u$把他换走了。那我们能不能先暂时用一个别的什么数先把这个位置上的数换掉,然后沿着回路走一圈,最后再把这个暂时存放的数换走呢?这样一个过程之后,异或和是没有发生改变的,那么其实这样等价于将$(u,v)$去掉,然后加上$(u,x),(x,v)$两条边,其中$x$可以跟$u,v$不在同一个回路中。这样我们就可以把不同的回路连在一起啦。注意这样弄完之后每个点的度数(出度-入度)是保持不变的。

还有一个问题,就是答案的走法不一定是一条回路,也就是起点不一定就是终点。这个可以通过一些方法(直接从度数计算)直接判出终点,然后从终点往起点连一条边,最后答案减一就能解决啦。

交的过程中RE+WA了几发,原因是写的时候陷入智障,忘记离散化了,直接拿了$10^9$左右的编号来建图。。。

代码:

#include <cstdio>
#include <cstring>
#include <map>
#define MAXN 200010
using namespace std;

namespace Pre_Gao{
    map<int,int> S;

    void insert(int x){ S[x]=0; }

    void pre_gao(){
        int now=0;
        for(map<int,int>::iterator it=S.begin();it!=S.end();it++)
            it->second=++now;
    }

    int get(int x){
        return S[x];
    }
}

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,m,S,T;
int g[MAXN],nume;
int e2[MAXN][2];
int d[MAXN];
int visit[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x){
    visit[x]=1;
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to])
            dfs(e[i].to);
}

int gao(){
    int res=0;
    for(int i=0;i<=n;i++)
        if(g[i]!=-1 && !visit[i]){
            dfs(i);
            res++;
        }
    if(visit[S]) res--;
    res+=nume;
    return res;
}

int main(){
    memset(g,-1,sizeof g);
    scanf("%d",&m);
    n=150000;
    for(int i=1;i<=m;i++){
        scanf("%d",&e2[i][1]);
        S^=e2[i][1];
        Pre_Gao::insert(e2[i][1]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&e2[i][0]);
        Pre_Gao::insert(e2[i][0]);
    }
    Pre_Gao::insert(S);
    Pre_Gao::pre_gao();
    for(int i=1;i<=m;i++){
        e2[i][0]=Pre_Gao::get(e2[i][0]);
        e2[i][1]=Pre_Gao::get(e2[i][1]);
    }
    S=Pre_Gao::get(S);
    for(int i=1;i<=m;i++){
        d[e2[i][0]]++;
        d[e2[i][1]]--;
        if(e2[i][0]^e2[i][1])
            addEdge(e2[i][0],e2[i][1]);
    }
    bool flag=0;
    if(d[S]==1){
        T=-1;
        for(int i=1;i<=n;i++)
            if(d[i]==-1){
                if(T!=-1){
                    puts("-1");
                    return 0;
                }
                T=i;
            }
        d[S]--;
        d[T]++;
        addEdge(T,S);
        flag=1;
    }else{
        T=S;
        for(int i=0;i<=n;i++)
            if(d[i]!=0){
                puts("-1");
                return 0;
            }
    }
    int ans=gao();
    if(flag) ans--;
    printf("%d\n",ans);
    return 0;
}

查看详细内容