codeforces 557D Vitaly and Cyclef(二分图染色)

题目链接：http://codeforces.com/problemset/problem/557/D

大意：

      给出n个点以及m条边，以及没条边的两个点，求最少添加几条边能得到一个奇环，以及添加边的方法数。

一道二分图的染色的讨论题

       二分图中只有树或偶环， 奇环不能存在二分图中（自己可以画画）， 所以我们可以用二分图的染色的方法来判断奇偶环或树。

分析：

     给n个点， 最多填加3条边，就一定能形成奇环， 所以添加的边的条数为0， 1， 2， 3；

       按照添加的边数进行讨论

添加3条边：-------原图的边为0

                     sum = n*(n-1)*(n-2)/6;

      添加2条边：-------原图没有边共顶点/各个顶点的度都不大于1

      sum = m*(n-2);

     添加0条边：-------原图中本身就有奇环

   sum = 1;

      添加1条边：------原图中只有树或偶环

                  sum = Σ(sw[i]-1)*sw[i]/2+(sb[i]-1)*sb[i]/2;（因为图不一定连通）

AC代码：

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 100005;
const int inf = 0x3f3f3f3f;
int degree[maxn], color[maxn];
int sw[maxn], sb[maxn];
vector<int> G[maxn];
int n, m;
int dfs(int u, int t, int x)
{
if(color[u] && color[u]!=t)
return -1;
if(color[u] && color[u]==t)
return 1;
if(t == 1)
sw[x]++;
else
sb[x]++;
color[u] = t;
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(dfs(v, -t, x)==-1)
return -1;
}
return 1;
}
int main()
{
int a, b, Max = 0;
memset(color, 0, sizeof(color));
memset(degree, 0, sizeof(degree));
memset(sw, 0, sizeof(sw));
memset(sb, 0, sizeof(sb));
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
{
scanf("%d%d", &a, &b);
degree[a]++;
degree[b]++;
Max = max(Max, degree[a]);
Max = max(Max, degree[b]);
G[a].push_back(b);
G[b].push_back(a);
}
int ans;
long long sum;
if(m == 0)
ans = 3, sum = (long long)n*(n-1)*(n-2)/6;
else if(Max <= 1)
ans = 2, sum = (long long)m*(n-2);
else
{
int flag = 0;
for(int i = 1; i <= n; i++)
if(!color[i])
{
if(dfs(i, 1, i) == -1)
{
flag = 1;
break;
}
}
if(flag)
ans = 0, sum = 1;
else
{
ans = 1, sum = 0;
for(int i = 1; i <= n; i++)
sum += (long long)sw[i]*(sw[i]-1)/2+(long long)sb[i]*(sb[i]-1)/2;
}
}
printf("%d %I64dn", ans, sum);
return 0;
}

最后

以上就是失眠砖头为你收集整理的codeforces 557D Vitaly and Cyclef(二分图染色)的全部内容，希望文章能够帮你解决codeforces 557D Vitaly and Cyclef(二分图染色)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。