Codeforces Round #311 (Div. 2) C(技巧) *D(二分图染色)

78 阅读 0 评论 52 点赞

我是靠谱客的博主魁梧牛排，最近开发中收集的这篇文章主要介绍Codeforces Round #311 (Div. 2) C(技巧) *D(二分图染色)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

C. Arthur and Table

http://codeforces.com/contest/557/problem/C

题意：一张桌子有n条桌腿，每条桌腿有相应的长度和移动花费值，要使桌子平稳，最长桌腿的数量M 与桌腿的数量关系为 M*2>N,求出使桌子平稳的最小花费值。

思路：将桌腿按照长度由大到小排序，依次以不同长度的桌腿cnt 作为桌子的平稳支撑，保留另外cnt-1条花费值大的桌腿，则可得到移动的桌腿的最小花费值。具体的做法是使用数组将所有的花费值个数存起来，遍历花费值200~1，求得cnt-1 条花费大的桌腿。

AC.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f;
const int maxn = 1e5 + 5;
struct node {
int len, d;
bool operator < (const node & A) const {
return len > A.len;
}
}leg[maxn];
int num[205];
bool cmp(node x, node y) {
return x.d < y.d;
}
int main()
{
//freopen("in", "r", stdin);
int n;
while(~scanf("%d", &n)) {
memset(num, 0, sizeof(num));
for(int i = 1; i <= n; ++i) {
scanf("%d", &leg[i].len);
}
int sum = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", &leg[i].d);
num[leg[i].d] ++;
sum += leg[i].d;
}
sort(leg+1, leg + n+1);
int res = 0, ans = 0, cnt = 0;
for(int i = 1; i <= n+1; ++i) {
if(i == 1 || leg[i].len == leg[i-1].len) {
res += leg[i].d;
num[leg[i].d]--;
cnt++;
}
else {
for(int j = 200;
j >= 1; --j) {
if(num[j] > 0) {
if(num[j] <= cnt-1) {
res += num[j]*j;
cnt -= num[j];
}
else
{
res += (cnt-1)*j;
cnt = 1;
}
}
if(cnt <= 1) break;
}
ans = max(ans, res);
res = leg[i].d;
cnt = 1;
num[leg[i].d]--;
}
}
printf("%dn", sum - ans);
}
return 0;
}

D. Vitaly and Cycle

http://codeforces.com/contest/557/problem/D

题意：无向图，有n个端点m条边，求出至少加入多少条边可得到奇数环，且这样的环有多少个。

思路：分析题目可知只会有4种情况：

1. 加入0条边，将图进行二分图染色可以判断，若图不为二分图则无需加边，存在一个奇环。

2. 加入3条边，图中没有边的情况。

3.加入1条边，对图进行二分图染色的时候记录每个连通块的黑白点个数，形成奇环时在同一个连通块中选择两个黑点或者两个白点，加入一条边得到奇环。

4.加入2条边，图不存在度大于等于2的点，则任选一个点和一条边组成奇环,总数为（n-2）*m。

AC.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e5+5;
vector<int> g[maxn];
int cnt[2], col[maxn];
int n, m;
vector<pair<int, int> > cal;
bool dfs(int u)
{
for(int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if(col[v] != -1) {
if(col[u] == col[v]) return false;
else continue;
}
col[v] = col[u]^1;
cnt[col[v]]++;
if(!dfs(v)) return false;
}
return true;
}
bool judge()
{
memset(col, -1, sizeof(col));
for(int i = 0; i < n; ++i) {
if(col[i] != -1) continue;
col[i] = 0;
cnt[0] = 1;
cnt[1] = 0;
if(!dfs(i)) return true;
cal.push_back(make_pair(cnt[0], cnt[1]));
}
return false;
}
int main()
{
//freopen("in", "r", stdin);
while(~scanf("%d %d", &n, &m)) {
for(int i = 0; i < n; ++i) {
g[i].clear();
}
cal.clear();
for(int i = 0; i < m; ++i) {
int u, v;
scanf("%d %d", &u, &v);
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
if(judge()) printf("0 1n");
else {
int ok = 0;
for(int i = 0; i < n; ++i) {
if(g[i].size() > 1) {
ok = 1;
break;
}
}
if(ok) {
long long ans = 0;
//printf("%d n", cal[0].first, cal[0].second);
for(int i = 0; i < cal.size(); ++i) {
ans += (long long)cal[i].first * (cal[i].first-1) / 2;
ans += (long long)cal[i].second * (cal[i].second - 1) / 2;
}
printf("1 %lldn", ans);
}
else {
if(m) {
printf("2 %I64dn", (long long)m*(n-2));
}
else {
printf("3 %lldn", (long long)n*(n-1)*(n-2)/6);
}
}
}
}
return 0;
}