이분 도 일치

Acwing 257 범인 수감
S 타 운 에는 현재 두 개의 교도소 가 있 으 며, 모두 N 명의 범죄자 가 수감 되 어 있 으 며, 번 호 는 각각 1 ~ N 이다.
그들 사이 의 관계 도 자연히 극히 조 화 롭 지 못 하 다.
많은 범죄자 들 사이 에 원한 이 쌓 여 객관 적 인 조건 이 갖 춰 지면 언제 든 충돌 이 일어 날 수 있다.
우 리 는 '원한 치' (하나의 정수 치) 로 어떤 두 범죄자 간 의 원한 정 도 를 나타 내 고 원한 치가 클 수록 이 두 범죄자 간 의 원한 이 많아 진다.
만약 에 두 명의 원한 이 c 인 범죄자 가 같은 감옥 에 갇 히 면 그들 둘 사이 에 마찰 이 발생 하고 영향력 이 c 인 충돌 사건 을 초래 할 것 이다.
매년 말 경찰 서 는 이 해 내 교도소 의 모든 충돌 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 으로 만 든 뒤 S 성 Z 시장 에 게 상신 한다.
공무 가 바 쁜 Z 시장 은 리스트 에 있 는 첫 사건 의 영향력 만 보 러 가 고, 영향 이 나 쁘 면 경찰국장 경질 을 검토 할 것 으로 보인다.
N 명 범죄자 간 갈등 관 계 를 상세히 살 펴 본 경찰 국장 은 스트레스 를 크게 받 았 다.
그 는 충돌 사건 의 영향력 이 작 아 자신의 감 투 를 지 키 기 위해 범죄자 들 을 두 감옥 에서 재분배 할 계획 이다.
같은 감옥 에 있 는 두 범죄자 사이 에 원한 이 있다 고 가정 하면 그들 은 매년 어느 순간 마찰 을 일 으 킬 것 이다.그렇다면 어떻게 범죄 자 를 배분 해 야 Z 시장 이 본 그 충돌 사건 의 영향력 을 최소 화 할 수 있 을 까?이 최소 치 는 얼마 입 니까?
 
입력 형식
첫 번 째 행 위 는 두 개의 정수 N 과 M 으로 각각 범인의 수 와 원한 이 있 는 범인의 대 수 를 나타 낸다.
다음 M 행 의 모든 행 위 는 세 개의 정수 aj, bj, cj 로 aj 호 와 bj 호 범죄자 사이 에 원한 이 존재 하고 그 원한 치 는 cj 임 을 나타 낸다.
데이터 보증 1 ≤ aj < bj < N, 0 < cj ≤ 100000000 범인 조합 은 한 번 씩 만 나타난다.
 
출력 형식
Z 시장 이 본 충돌 사건 의 영향력 을 위해 총 1 줄 을 수출 한다.
올해 안에 감옥 에서 충돌 사건 이 발생 하지 않 았 다 면 0 을 출력 하 십시오.
 
데이터 범위
N≤20000,M≤100000
 
입력 예시:

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

 
출력 예시:

3512

//     
#include
using namespace std;
const int N = 1e5 + 7;
int par[N], n, m;
struct Node {
    int x, y, c;
}e[N];
int find(int x) {
    return x == par[x] ? x : par[x] = find(par[x]);
}
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    par[fx] = fy;
}
bool same(int x, int y) {
    return find(x) == find(y);
}
void init() {
    for (int i = 0; i < N; i++) par[i] = i;
}
bool check(int x) {
    init();
    for (int i = 1; i <= m; i++) {
        if (e[i].c <= x) continue;
        if (same(e[i].x, e[i].y)) return false;
        merge(e[i].x + n, e[i].y);
        merge(e[i].x, e[i].y + n);
    }
    return true;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].c);
    int l = 0, r = 1e9;
    while (l <= r) {
        int k = (l + r) >> 1;
        if (check(k))
            r = k - 1;
        else
            l = k + 1;
    }
    printf("%d
", l);
    return 0;
}

 

//     
#include
using namespace std;
const int N = 2e5 + 7;
namespace Graph {
    int head[N], ver[N], nex[N], col[N], tot, n, f;
    void init(int x) {
        tot = 0; f = 0;
        n = x;
        memset(col, 0, sizeof(col));
        memset(head, 0, sizeof(head));
    }
    void add(int x, int y) {
        ver[++tot] = y;
        nex[tot] = head[x];
        head[x] = tot;
    }
    void printGraph() {
        for (int i = 1; i <= n; i++) {
            printf("%d: ", i);
            for (int j = head[i]; j; j = nex[j]) {
                printf("%d ", ver[j]);
            }
            printf("
");
        }
    }
    void dfs(int x, int c) {
        col[x] = c;
        for (int i = head[x]; i; i = nex[i]) {
            int y = ver[i];
            if (!col[y])
                dfs(y, 3 - c);
            else if (col[y] == c) {
                f = 1;
            }
        }
    }
    void solve() {
        for (int i = 1; i <= n; i++) {
            if (!col[i]) dfs(i, 1);
        }
    }
    int status() {
        return f;
    }
}
struct Node {
    int x, y, c;
}e[N];
int n, m;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].c);
    int l = 0, r = 1e9;
    while (l <= r) {
        int k = (l + r) >> 1;
        Graph::init(n);
        for (int i = 1; i <= m; i++) {
            if (e[i].c > k) {
                Graph::add(e[i].x, e[i].y);
                Graph::add(e[i].y, e[i].x);
            }
        }
        //Graph::printGraph();
        Graph::solve();
        //printf("%d
", Graph::f);
        if (!Graph::status())
            r = k - 1;
        else
            l = k + 1;
    }
    printf("%d
", l);
    return 0;
}

 
Acwing 372 바둑판 커버
N 줄 N 열의 바둑판 을 지정 합 니 다. 일부 칸 은 설치 가 금지 되 어 있 습 니 다.
바둑판 에 최대 몇 개의 길 이 를 2, 너비 가 1 인 골 패 를 놓 을 수 있 는 지, 골 패 의 경계 와 격 선 이 겹 치고 (골 패 는 두 개의 칸 을 차지한다), 임의의 두 장의 골 패 는 겹 치지 않 는 다.
입력 형식
첫 번 째 줄 에는 두 개의 정수 N 과 t 가 포함 되 어 있 으 며, 그 중에서 t 는 설치 가 금 지 된 칸 의 수량 입 니 다.
다음 t 줄 은 각 줄 에 두 개의 정수 x 와 y 를 포함 하고 x 줄 의 y 열 에 있 는 칸 은 배치 가 금지 되 어 있 으 며 행렬 수 는 1 부터 시작 합 니 다.
출력 형식
하나의 정 수 를 출력 하여 결 과 를 표시 하 다.
데이터 범위
1≤N≤100
출력 예시:

8 0

출력 예시:

32

#include
#include
using namespace std;
typedef long long LL;
const int N = 2e2 + 7;
int a[N][N], head[N * N], nex[N * N], vis[N * N], ver[N * N], match[N * N], tot;
const int delta[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
namespace MyStd {
#define isDigit(ch) (ch >= '0' && ch <= '9')

    inline int read() {
        char ch = getchar();
        int x = 0, f = 1;
        while (!isDigit(ch)) {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (isDigit(ch)) {
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return x * f;
    }
    inline int max(int x, int y) { return x < y ? y : x; }
    inline int min(int x, int y) { return x < y ? x : y; }
    template
    inline T ksm(T a, T b, T mod) {
        T ans = 1;
        while (b) {
            if (b & 1) ans = ans * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return ans;
    }
}
void add(int x, int y) {
    ver[++tot] = y;
    nex[tot] = head[x];
    head[x] = tot;
}
bool dfs(int x) {
    for (int i = head[x]; i; i = nex[i]) {
        int y = ver[i];
        if (!vis[y]) {
            vis[y] = 1;
            if (!match[y] || dfs(match[y])) {
                match[y] = x; return true;
            }
        }
    }
    return false;
}
int solve(int n) {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if ((i + j) & 1 || a[i][j]) continue;
            memset(vis, 0, sizeof(vis));
            if (dfs((i - 1) * n + j)) ans++;
        }
    }
    return ans;
}
int main() {
    int n = MyStd::read();
    int t = MyStd::read();
    while (t--) {
        int x = MyStd::read();
        int y = MyStd::read();
        a[x][y] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if ((i + j) & 1 || a[i][j]) continue;
            for (int k = 0; k < 4; k++) {
                int x = i + delta[k][0];
                int y = j + delta[k][1];
                if (x >= 1 && x <= n && y >= 1 && y <= n && !a[x][y]) {
                    add((i - 1) * n + j, (x - 1) * n + y);
                }
            }
        }
    }
    printf("%d
", solve(n));
    return 0;
}