Homework

#include <bits/stdc++.h>

using namespace std;

#define llong long long int

const llong INF = 1e9 + 7;

class Dinic{
    int N;
    vector<llong> level;
    vector<bool> dead;

public:
    struct Edge{
        Edge(int a,llong x){
            v = a;
            cap = x;
        }
        int v;
        llong cap;
    };
    int source;
    int sink;
    vector<Edge> edge;
    vector<vector<int>> g;

    Dinic(int n){
        g.resize(n);
        N = n;
        level.resize(n);
    }

    void setInit(int u,int v){
        source = u;
        sink = v;
    }

    void addEdge(int u,int v,llong cap){
        g[u].push_back(edge.size());
        edge.push_back(Edge(v,cap));
        g[v].push_back(edge.size());
        edge.push_back(Edge(u,0));
    }
private:

    bool BFS(){

        for(int i=0;i<N;i++) level[i] = INF;
        level[source] = 0;
        queue<int> q;
        q.push(source);

        while(!q.empty()){

            int u = q.front();
            q.pop();

            if(u == sink) return true;

            for(auto x: g[u]){
                if(level[edge[x].v] == INF && edge[x].cap > 0){
                    level[edge[x].v] = level[u] + 1;
                    q.push(edge[x].v);
                }
            }
        }
        return false;
    }

    llong maxflow(int u,llong flow){

        llong ret = 0;
        llong f = 0;
        if(flow == 0) return 0;
        if(u == sink) return flow;

        for(auto i: g[u]){
            if(level[edge[i].v] != level[u] + 1) continue;
            f = maxflow(edge[i].v,min(edge[i].cap,flow));
            int x = (i%2 == 0?i+1:i-1);
            flow -= f;
            ret += f;
            edge[i].cap -= f;
            edge[x].cap += f;
        }

        if(ret == 0) level[u] = INF;

        return ret;
    }
public:
    llong run(){

        llong flow = 0;
        while(BFS()){
            flow += maxflow(source,INF);
        }

        return flow;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<int> diff(n, 0);
    Dinic solver(n + m + 2);
    int src = 0, snk = n + m + 1;

    for (int i = 1; i <= m; i++) {
        int u, v, d;
        cin >> u >> v >> d;

        if (!d) {
            diff[u - 1]++;
            diff[v - 1]++;

            solver.addEdge(src, i, 1);
            solver.addEdge(i, m + u, 1);
            solver.addEdge(i, m + v, 1);
        } else {
            diff[u - 1]++;
            diff[v - 1]--;
        }
    }

    int sum = 0;
    bool possible = true;

    for (int i = 0; i < n && possible; i++) {
        if (diff[i] < 0 || (diff[i] & 1)) possible = false;
        else {
            sum += diff[i] / 2;
            solver.addEdge(m + i + 1, snk, diff[i] / 2);
        }
    }

    if (!possible) cout << "NO\n";
    else {
        solver.setInit(src, snk);
        possible = solver.run() == sum;
        cout << (possible ? "YES" : "NO") << "\n";
    }
}