本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P1525
应该说这道题不算太难，但挺考察代码实现能力。首先我们应该是本着贪心的原则，让怨气值大的罪犯尽量分开，这样就牵扯到将n个点划分成两部分的问题。做法有两种，并查集或二分答案+二分图染色。值得一提的是并查集（懒），这里get到了一个新技能：补集。
一开始，我判断的方法是，将不能在一起的罪犯加入到一个并查集，如果遇到冲突（两个罪犯原先就在一个并查集里）则为判定失败，这样只有60分。哪里不对呢？举个简单的例子，A和B不能在一起，B和C不能在一起，C和D不能在一起，按照上面的方法，A和D也不能在一起，但实际上A和D可以在一起，这牵扯到两个点之间隔着奇数个点还是偶数个点。
然后看到dalao题解里有种方法是使用补集，就是把不能和某个罪犯在一起的罪犯放到一起，因为只有两个牢房，如果放到一起的罪犯不能在一起，这就是真的冲突了。使用补集要注意一开始初始化时，补集里的元素也要和其他元素一样初始化父亲为自己。
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 6 inline int get_num() { 7 int num = 0; 8 char c = getchar(); 9 while (c < '0' || c > '9') c = getchar(); 10 while (c >= '0' && c <= '9') 11 num = num * 10 + c - '0', c = getchar(); 12 return num; 13 } 14 15 const int maxn = 2e4 + 5, maxm = 1e5 + 5; 16 17 struct Edge { 18 int u, v, w; 19 bool operator < (const Edge& rhs) const { 20 return w > rhs.w; 21 } 22 } edge[maxm]; 23 24 int fa[2 * maxn]; 25 26 int dj_find(int i) { 27 if (i == fa[i]) return i; 28 else return fa[i] = dj_find(fa[i]); 29 } 30 31 inline void dj_merge(int a, int b) { 32 fa[dj_find(a)] = dj_find(b); 33 } 34 35 int main() { 36 int n = get_num(), m = get_num(); 37 for (int i = 1; i <= m; ++i) 38 edge[i]. u = get_num(), edge[i].v = get_num(), edge[i].w = get_num(); 39 sort(edge + 1, edge + m + 1); 40 for (int i = 1; i <= 2 * n; ++i) fa[i] = i; 41 for (int i = 1; i <= m; ++i) { 42 int u = edge[i].u, v = edge[i].v; 43 if (dj_find(u) == dj_find(v)) { 44 printf("%d", edge[i].w); 45 return 0; 46 } else { 47 dj_merge(u, v + n); 48 dj_merge(v, u + n); 49 } 50 } 51 printf("0"); 52 return 0; 53 }