ZJT's Blog

大変に気分がいい~

集训队作业之AGC018-F

2017-12-18 12:312017-12-18 12:31
集训队作业AtCoder构造二分图

传送门

首先我们可以直接根据每个点的儿子个数来确定这个点权值的奇偶性。如果某个点在两棵树里的奇偶性不一样,则显然无解。否则,我们可以通过以下方法构造出一组解,使得权值为偶数的点全部取$0$,剩下的点要么是$1$要么是$-1$。

对于每棵树,我们可以把所有奇数的点两两配对(由于奇数点的数量是奇数,所以会剩下一个点不参与配对),使得对于每棵子树,设子树中的奇数点有$2k+1$个,我们都可以在子树中找出$k$对配对的奇数点(还有一个点没有在子树内部配对)。则我们可以钦定每对点一个取$1$,一个取$-1$,这样每个子树的权值和的绝对值就是$1$了。

我们把两棵树的配对情况都拿出来连边,这样建出来的图显然是不含奇环的,所以是个二分图。我们直接把二分图左边的点赋成$1$,右边的点赋成$-1$,就能满足条件了。

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

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

int n,root;
int g[MAXN],nume;
int e2[MAXN][2],nume2;
int d[MAXN],d0[MAXN];
int c[MAXN];

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

int dfs(int x){
    int cnt=0;
    int last=0;
    for(int i=g[x];~i;i=e[i].next){
        cnt^=1;
        int temp=dfs(e[i].to);
        nume2++;
        if(last){
            e2[nume2][0]=last;
            e2[nume2][1]=temp;
            last=0;
        }else last=temp;
    }
    if(!last) last=x;
    d[x]^=cnt;
    d0[x]=cnt;
    return last;
}

void dfs2(int x){
    for(int i=g[x];~i;i=e[i].next)
        if(!c[e[i].to]){
            c[e[i].to]=-c[x];
            dfs2(e[i].to);
        }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d",&n);
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        if(t!=-1) addEdge(t,i);
        else root=i;
    }
    dfs(root);
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        if(t!=-1) addEdge(t,i);
        else root=i;
    }
    dfs(root);
    for(int i=1;i<=n;i++)
        if(d[i]){
            puts("IMPOSSIBLE");
            return 0;
        }
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=nume2;i++)
        addEdge(e2[i][0],e2[i][1]),addEdge(e2[i][1],e2[i][0]);
    for(int i=1;i<=n;i++)
        if(!d0[i] && !c[i]){
            c[i]=1;
            dfs2(i);
        }
    puts("POSSIBLE");
    for(int i=1;i<=n;i++)
        if(d0[i]) printf("0 ");
        else printf("%d ",c[i]);
}

查看详细内容

集训队作业之ARC080-F

2017-10-25 8:162017-10-25 8:16
集训队作业AtCoder二分图

传送门

记$a_i$为第$i$个数的初始颜色,$a_i=1$表示第$i$个数初始为黑色,我们的目标是翻转一些区间,使得所有数变成白色。首先发现对于长度不是奇质数的区间,我们也可以通过一些步骤来翻转这段区间颜色。对于每个偶数,我们可以用两个奇质数的差来表示这个偶数(然而这个怎么证啊),所以可以用两步翻转一个偶长度区间。剩下的非质数的奇数,就只能用三步翻转了(先把靠在左边长度为3的区间翻转,剩下的长度就是偶数了)。我们把第$i$个数和第$i+1$个数之间的空隙看成$i$号点,并把翻转区间$[l,r]$看作结点$l-1$和结点$r$之间的一条边,边权只会是$1/2/3$。显然,如果一个点$x$连出去两条边$(x,y),(x,z)$,那么这跟一条边$(y,z)$是等价的,并且后者的权值不会大于前者的权值和。所以最优情况下每个点的度数最多为1。考虑那些$a_i\ne a_{i+1}$的$i$,$i$号点的度数必须为1(因为要保证第$i$个数被区间的覆盖次数不等于第$i+1$个数被覆盖的次数,$i$号点有边连出去的话就能保证了),否则$i$号点的度数必须为0。这样,在删去度数为0的点后,我们要选一些边,使得每个点的度数均为1,并且总边权和最小。然后。。。

这tm不就是最小权一般图完美匹配吗。。。然而我不会带权带花树啊,而且这是ARC的F啊,ARC都出带花树,那是不是有点世风日下啊??

想了半天也还是只会一般图匹配啊,因为不想学带权带花树,所以只能看题解啦。题解也是基于这个模型,但是把$i$为奇数的点和$i$为偶数的点分成了两组,任意边权为$1/3$的边都是连接不同组的点的,而任意同组的点之间都有边权为$2$的边。考虑连了$k$条边权为1的边,对于剩下的点,我们可以尽量的取边权为2的边,也就是两个两个的连边。这样的话,每一组可能同时剩下一个点,也可能恰好连完。注意到这个的总权值是关于$k$单调减的,所以我们直接最大化边权为1的边,也就是跑一个二分图最大匹配就做完啦。

这种题的建模还是比较奥妙的,像我这样的傻子一般都是推到一半就卡住推不下去了。。。只能靠多做点题提高一个了吧。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define MAXN 210
#define MAXM 10000010
using namespace std;

struct edge{
    int to,next,w;
    edge(int _to=0,int _next=0,int _w=0):to(_to),next(_next),w(_w){}
}e[MAXM];

int n,m,S,T;
int g[MAXN],nume;
bool flag[MAXM];
int prime[MAXM],nump;
int p0[MAXN],p[MAXN],tag[MAXN];
int level[MAXN];

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

void init(){
    flag[1]=1;
    for(int i=2;i<MAXN;i++){
        if(!flag[i]) prime[++nump]=i;
        for(int j=1;j<=nump && i*prime[j]<MAXN;j++){
            flag[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
    flag[2]=1;
}

bool bfs(){
    memset(level,-1,sizeof level);
    static queue<int> Q;
    Q.push(S);
    level[S]=0;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=g[x];~i;i=e[i].next)
            if(e[i].w && level[e[i].to]==-1){
                level[e[i].to]=level[x]+1;
                Q.push(e[i].to);
            }
    }
    return level[T]!=-1;
}

int dfs(int x,int delta){
    if(x==T) return delta;
    if(!delta) return 0;
    int res=0;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].w && level[e[i].to]==level[x]+1){
            int temp=dfs(e[i].to,min(delta,e[i].w));
            delta-=temp;
            res+=temp;
            e[i].w-=temp;
            e[i^1].w+=temp;
            if(!delta) return res;
        }
    return res;
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    init();
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%d",p0+i);
    p[++n]=p0[1]-1;
    for(int i=1;i<m;i++)
        if(p0[i]+1<p0[i+1]){
            p[++n]=p0[i];
            p[++n]=p0[i+1]-1;
        }
    p[++n]=p0[m];
    int c0=0,c1=0;
    for(int i=1;i<=n;i++)
        if(p[i]&1) tag[i]=1,c1++;
        else c0++;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!tag[i] && tag[j] && !flag[abs(p[i]-p[j])])
                addEdge(i,j,1);
    S=n+1; T=n+2;
    for(int i=1;i<=n;i++)
        if(tag[i]) addEdge(i,T,1);
        else addEdge(S,i,1);
    int flow=0;
    while(bfs()) flow+=dfs(S,0x77777777);
    int ans=flow+((c0-flow)/2+(c1-flow)/2)*2+((c0-flow)%2)*3;
    printf("%d\n",ans);
}

查看详细内容