ACwing 257 - detaining criminals (dichotomous answer + dichotomous coloring)

There are two prisons in S City, holding a total of N criminals, numbered 1~N respectively.

Naturally, the relationship between them is also extremely disharmonious.

Many criminals have even accumulated grievances for a long time. If the objective conditions are met, conflicts may break out at any time.

We use "resentment value" (a positive integer value) to express the degree of hatred between two criminals. The greater the resentment value, the more resentment between the two criminals.

If two criminals with a grievance value of c are held in the same prison, there will be friction between them and lead to a conflict with an influence of c.

At the end of each year, the police station will make a list of all conflicts in the prison this year, from large to small, and then report to mayor Z of S city.

Busy mayor Z will only look at the influence of the first event on the list. If the influence is very bad, he will consider replacing the police chief.

After a detailed investigation of the contradictory relationship between N criminals, the police chief felt great pressure.

He plans to redistribute the criminals in the two prisons so that the conflict will have less influence, so as to keep his black hat.

Suppose that as long as there is hatred between two criminals in the same prison, they will have friction at some time of the year. So how should criminals be allocated to minimize the impact of the conflict seen by Mayor Z? What is the minimum value?

Input format

The first line is two positive integers N and M, which respectively represent the number of criminals and the number of criminals with hatred.

In the next M line, there are three positive integers aj, bj and cj for each line, indicating that there is hatred between criminals aj and BJ, and their resentment value is cj.

The data guarantee is 1 ≤ AJ < BJ < n, 0 < CJ ≤ 1000000000, and each combination of criminals only occurs once.

Output format

Output a total of 1 line, which is the influence of the conflict event seen by Mayor Z.

If there is no conflict in the prison this year, please output 0.

Data range

N≤20000,M≤100000

Input sample:

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

Output example:

3512

Main idea of the title:

Give the relationship between n criminals and M pairs, and then there are m lines. Enter three numbers a, b and W in each line, indicating that the anger value of criminal a and criminal b is w. as long as two criminals with holidays are in the same cell, they will fight and produce events with the influence of their anger value W. now there are two prisons, you need to reasonably allocate these prisoners to minimize their influence on events.

Problem solving ideas:

If limit > is a dichotomous graph, it can be divided into two parts. If limit > is a dichotomous graph, it can be divided into two parts. If limit > is a reasonable dichotomous graph, it can determine whether all prisoners can be divided into two parts. If limit > is a dichotomous graph, it can be divided into two parts, If you can't form a bipartite graph, you should increase the anger value and dye it every time.

Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) x & (-x)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 2e4 + 50;
const int M = 1e5 + 50;

int h[N], e[2 * M], w[2 * M], ne[2 * M], idx;
int n, m;
int color[N];

void add(int a, int b, int c)//Adjacency table storage map
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool dfs(int u, int c, int lmt)
{
    color[u] = c;
    
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (w[i] <= lmt) continue;//Judge only criminals with influence > = limit
        if (!color[j])
        {
            if (!dfs(j, 3 - c, lmt)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check(int s)//Judgement bipartite graph by coloring method
{
    memset(color, 0, sizeof color);

    for (int i = 1; i <= n; i ++)
        if (!color[i])
            if (!dfs(i, 1, s)) 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;
}

Tags: C++ Algorithm Graph Theory partitioning dfs

Posted by hame22 on Fri, 20 May 2022 15:31:44 +0300