Ta coi mỗi học sinh là một nút trong đồ thị và các mối quan hệ bạn bè là cạnh của đồ thị

Subtask 1

Ta sẽ sinh nhị phân để chia các học sinh thành 2 bên và tính tổng sức mạnh.

Subtask 2

Nhận xét: Độ chênh lệch sức mạnh giữa 2 nhóm bằng độ chênh lệch tổng bậc ở các nút chia ~2~

Giải thích: nếu một cạnh có giá trị là ~v~ nằm ở một nhóm thì tổng bâc ở nhóm đó được cộng thêm ~2v~, ngược lại nếu cạnh đó nối với 2 đỉnh ở 2 nhóm khác nhau thì tổng bậc ở mỗi nhóm sẽ được tăng thêm ~v~ và chênh lệch không hề thay đổi.

Vậy ta có công thức quy hoạch động ~dp[i][cnt][sum] = true/false~ tức là xét đến học sinh thứ ~i~ và đã lựa chọn ~cnt~ học sinh vào nhóm 1 trong số các học sinh từ ~1 \rightarrow i - 1~ và tổng bậc của nhóm 1 là ~sum~.

Cách chuyển trạng thái giống như bài toán quy hoạch động cái túi cơ bản nên xin nhường lại cho bạn đọc.

Độ phức tap: ~\mathcal{O}(n^4)~

Subtask 3

Hàm quy hoạch động của ta có thể dùng bitset để chuyển trạng thái nhanh hơn. Cụ thể các bạn có thể đọc comment này trên codeforces.

Code mẫu

// Make the best become better
// No room for laziness
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 400 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e9;
int n, m;
int deg[maxN];
bitset<maxN * maxN> f[2][maxN];
int sum = 0;
void ReadInput()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        deg[u] += w;
        deg[v] += w;
        sum += 2 * w;
    }
}
void Solve()
{
    f[0][0][0] = 1;
    for(int i=1; i<=2*n; i++)
        for(int j=0; j<=min(i, n); j++)
        {
            f[i & 1][j] |= f[(i & 1) ^ 1][j];
            if(j) f[i & 1][j] |= f[(i & 1) ^ 1][j - 1] << deg[i];
        }
    int res = oo;
    for(int i=0; i<=n*n*4; i++)
        if(f[0][n][i])
        {
            res = min(res, abs((sum - i * 2) / 2));
        }
    cout << res;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}