Codeforces Round #429 (Div. 2) - D Leha and another game about graph

Leha and another game about graph

题目大意：给你一个图，每个节点都有一个v( -1 , 0 ,1)值，要求你选一些边，使v值为1

的点度数为奇数，v值为0的度数为偶数，v值为-1的节点没有限制。让你输出边的集合，

如果不存在这样的边集，输出-1。

写的时候没啥思路，dfs瞎搞了一下过不了。

思路：我们先考虑没有解的情况，如果v值为1的点为奇数个，且没有v为-1的点，则不存在

解，因为你添加一条边改变了两个v值非-1点的奇偶性，又有奇数个v值为1的点，不可能满足

全部点，所以不存在解。然后我们把当前节点只和它的父节点联系在一起，如果当前节点

不满足条件，就加上它和它父节点之间的那条边，这里如果有v位-1的点，我们优先用它作为

根节点，因为子节点必定满足了条件，只要看根节点就行了。

#include<bits/stdc++.h>

#define ll long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int,int>

#define pb push_back

using namespace std;

const int N=*1e5+;

int v[N],n,m;

vector<pii> e[N];

vector<int> ans;

bool vis[N],e_vis[N];

void dfs(int u,int e_id)

{

    vis[u]=true;

    bool flag=false;

    int len=e[u].size();

    for(int i=;i<e[u].size();i++)

    {

        pii p=e[u][i];

        if(vis[p.fi]) continue;

        dfs(p.fi,p.se);

        if(e_vis[p.se]) flag=!flag;

    }

    if(v[u]==- || flag==v[u]) return;

    if(e_id!=-)

    {

        e_vis[e_id]=true;

        ans.pb(e_id);

    }

}

int main()

{

    cin>>n>>m;

    int st=-,sum=;

    for(int i=;i<=n;i++)

    {

        scanf("%d",&v[i]);

        if(st==- && v[i]==-) st=i;

        if(v[i]!=-) sum+=v[i];

    }

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

    {

        int f,t; scanf("%d%d",&f,&t);

        e[f].pb(mk(t,i));

        e[t].pb(mk(f,i));

    }

    //cout<<st<<endl;

    if(st==- && sum&)

    {

        puts("-1");

        return ;

    }

    if(st==-) dfs(,-);

    else dfs(st,-);

    int len=ans.size();

    sort(ans.begin(),ans.end());

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

    for(int i=;i<len;i++) printf("%d\n",ans[i]);

    return ;

}

巴特西

Codeforces Round #429 (Div. 2) - D Leha and another game about graph

最新文章

热门文章