Submission #70048458

---

Source Code Expand

//*/
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<pair<int, int> > edges(m);
    for (int i=0; i<m; i++) {
        cin >> edges[i].first >> edges[i].second;
        edges[i].first--;
        edges[i].second--;
    }
    int ans = m;
    // 看到数据量极小，借助二进制枚举所有染色方案
    for (int mask=0; mask<(1<<n); mask++) {
        int cnt = 0;
        for (auto e : edges) {
            int u = e.first, v = e.second;
            if (((mask>>u) & 1) == ((mask>>v) & 1)) {
                cnt++;
            }
        }
        ans = min(ans, cnt);
    }
    
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result