正文
Codeforces Round #311 (Div. 2) D - Vitaly and Cycle(二分图染色应用)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
http://www.cnblogs.com/wenruo/p/4959509.html
给一个图（不一定是连通图，无重边和自环），求练成一个长度为奇数的环最小需要加几条边，和加最少边的方案数。
很容易知道连的边数只能是0,1,2,3。
如果是二分图一定不含长度为奇数的环。
难点是如果是二分图怎么求方案数呢？
二分图染色时能求出每一个联通块。在每一个联通块中把任意两个颜色相同的点连一条边即可达到要求。
如图中红色和绿色的边就是部分可行解
代码（含注释）：
/*****************************************************
Memory: 9380 KB Time: 155 MS
Language: GNU G++ 4.9.2 Result: Accepted
*****************************************************/
#include<bits/stdc++.h> using namespace std;
typedef long long ll; const int N = 100005; int color[N];
vector<int> G[N];
int degree[N];
int kind[N];
int sumk[N];
int colk[N]; bool dfs(int v, int clr, int kd)
{
color[v] = clr;
kind[v] = kd;
for (unsigned i = 0; i < G[v].size(); ++i)
{
int u = G[v][i];
if (!color[u])
{
if (!dfs(u, 3 - clr, kd))
return false;
}
else if (color[u] == clr) return false;
}
return true;
} void solve(int n)
{
/** 每一坨中点有多少个 每一坨中颜色为1的点有多少个*/
for (int i = 1; i <= n; ++i)
{
sumk[kind[i]]++;
if (color[i] == 1) colk[kind[i]]++;
}
} int main()
{
std::ios::sync_with_stdio(false);
int n, m;
cin >> n >> m; int a, b;
for (int i = 0; i < m; ++i)
{
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
degree[a]++;
degree[b]++;
} /**没有边,需要随意连接三个点 C(n,3)*/
if (m == 0)
{
cout << "3 " << (ll)n * (n - 1) * (n - 2) / 3 / 2;
return 0;
} /**每个边的长度都等于1，那么随便找一个边再连一个点就好了*/
int cnt = 0;
for (int i = 1; i <= n; ++i)
if (degree[i] > 1)
{
cnt = -1;
break;
}
else if (degree[i] == 1)
{
cnt++;
}
if (cnt != -1)
{
cout << "2 " << (ll)cnt / 2 * (n - 2);
return 0;
} /** 二分图匹配，如果不成 证明有奇长度的环 */
int kd = 0;
for (int i = 1; i <= n; ++i)
{
if (!color[i])
if (!dfs(i, 1, kd++))
{
kd = -1;
break;
}
}
if (kd == -1)
{
cout << "0 1";
return 0;
} /** 如果没有奇数环，所要做的就是找到两个同一堆的点中颜色相同的，随便连 */
ll ans = 0;
solve(n);
for (int i = 0; i < kd; ++i)
{
//cout << colk[i] << " " << sumk[i] << endl;
ans += (ll)colk[i] * (colk[i] - 1) + (ll)(sumk[i] - colk[i]) * (sumk[i] - colk[i] - 1);
}
cout << "1 " << ans / 2; return 0;
}
