首页 > 其他 > 详细

CodeForces 862B(思维+二分图染色)

时间:2019-12-08 12:03:42      阅读:89      评论:0      收藏:0      [点我收藏+]

题意

https://vjudge.net/problem/CodeForces-862B

给出n个点,n-1条边,求再最多再添加多少边使得二分图的性质成立

思路

因为题目是求的最多添加多少边,所以可以对树01染色,然后让每个0点连上所有的黑点,一共有0的个数*1的个数条边。再减去树的n-1条边即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
vector<int> g[N];
ll col[N],num[2];
void dfs(int u,int fa)
{
    for(int v:g[u])
    {
        if(v==fa)
            continue;
        col[v]=col[u]^1;
        num[col[v]]++;
        dfs(v,u);
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1; i<n; i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    num[0]++;
    col[1]=0;
    dfs(1,0);
    cout<<num[0]*num[1]-(n-1)<<endl;
    return 0;
}

  

CodeForces 862B(思维+二分图染色)

原文:https://www.cnblogs.com/mcq1999/p/12004735.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!