【CodeForces】841D. Leha and another game about graph（Codeforces Round #429 (Div. 2)）

【题意】给定n个点和m条无向边（有重边无自环），每个点有权值di=-1,0,1，要求仅保留一些边使得所有点i满足：di=-1或degree%2=di，输出任意方案。

【算法】数学+搜索

【题解】

最关键的一步：★【%2转取反】。

首先考虑在树上做这样的问题，就显得十分朴素了。每当选择一条边，边的两端点权值就会取反，所以做一次DFS，对儿子权值（变化后）为1的点连边，自身取反，儿子都处理完毕后再把自身的新权值反馈上去。这样本质上等同于，所有点权为1的点都通过路径将取反信息传递到根，若最终根权为0则问题解决且得到一种路径方案，若根权为1则需要换一个di=-1的点作为根重新dfs，若无则无解。（实际操作中直接先找-1的点DFS，没有再找任意一个判断有无解）

最后考虑图转树的正确性，需要论证一下两点：

1.图上的环没有影响：对于一个环，环边对环中所有点的度均为2，此时可以一起删去则模2不受影响。

2.图转成任意生成树没有影响：因为转成树后不管树长成什么样，都是所有的di=1的点在传递信息，简单的说，答案有解当且仅当【di=1的点为偶数个】或【di=1的点为奇数个且存在di=-1的点】，所以生成树的形态只是为了找到一个可行方案来输出，不会影响答案。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=;

struct edge{int v,from;}e[maxn*];

int first[maxn],d[maxn],n,m,ans=,tot=;

bool vis[maxn],a[maxn*];

void insert(int u,int v){

    tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;

    tot++;e[tot].v=u;e[tot].from=first[v];first[v]=tot;

}

int dfs(int x){

    vis[x]=;

    for(int i=first[x];i;i=e[i].from)if(!vis[e[i].v]){

        if(dfs(e[i].v)&){

            a[i]=;ans++;

            if(d[x]!=)d[x]=-d[x];

        }

    }

    return d[x];

}

int main(){

    scanf("%d%d",&n,&m);

    int point=;

    for(int i=;i<=n;i++){scanf("%d",&d[i]);if(d[i]==-)point=i,d[i]=;}

    int u,v;

    for(int i=;i<=m;i++){

        scanf("%d%d",&u,&v);

        insert(u,v);

    }

    if(point)dfs(point);

    else if(dfs()&){printf("-1");return ;}

    printf("%d\n",ans);

    for(int i=;i<=tot;i+=)if(a[i]||a[i+])printf("%d ",(i+)/);

    return ;

}

巴特西

【CodeForces】841D. Leha and another game about graph（Codeforces Round #429 (Div. 2)）

最新文章

热门文章