aso推广公司,广州网站关键词优化推广,WordPress用云数据库,纳税服务平台题意#xff1a;
S城现有两座监狱#xff0c;一共关押着N名罪犯#xff0c;编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久#xff0c;如果客观条件具备则随时可能爆发冲突。我们用“怨气值”#xff08;一个正整数值#xff09;来表示某两名罪…题意
S城现有两座监狱一共关押着N名罪犯编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久如果客观条件具备则随时可能爆发冲突。我们用“怨气值”一个正整数值来表示某两名罪犯之间的仇恨程度怨气值越大则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱他们俩之间会发生摩擦并造成影响力为c的冲突事件。
每年年末警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力如果影响很坏他就会考虑撤换警察局长。
在详细考察了N名罪犯间的矛盾关系后警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配以求产生的冲突事件影响力都较小从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨那么他们一定会在每年的某个时候发生摩擦。那么应如何分配罪犯才能使Z市长看到的那个冲突事件的影响力最小这个最小值是多少
题解
二分染色法判断二分图 题目要求我们找到将点分为两组使得各组内边的权值的最大值尽可能小 我们就二分一个limit当limit固定后因为我们要将所有点分为两组这样边就存在两组情况一种是在组内一种是在组间我们的答案是要记录组内的所有我们要让大于limit的边都在组间那么剩下在组内的边都是小于limit的。 我们用染色法判断大于limit的边也就说组间的边能否构成二分图 染色法判二分图复杂度是O(nm) 二分是logC 总的复杂度O((NM)logC)
代码
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 20010, M 200010;int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}bool dfs(int u, int c, int limit)
{color[u] c;for (int i h[u]; ~i; i ne[i]){if (w[i] limit) continue;int j e[i];if (color[j]){if (color[j] c) return false;}else if (dfs(j, 3 - c, limit)0) return false;}return true;
}bool check(int limit)
{memset(color, 0, sizeof color);for (int i 1; i n; i )if (color[i] 0)if (!dfs(i, 1, limit))return false;return true;
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof h);while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);add(b, a, c);}int l 0, r 1e9;while (l r){int mid l r 1;if (check(mid)) r mid;else l mid 1;}printf(%d\n, l);return 0;
}
