C++(clang++ 11.0.1) 解法, 执行用时: 18ms, 内存消耗: 4868K, 提交时间: 2022-11-28 11:07:27

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P ;
const int maxn = 4e4 + 10, INF = 0x3f3f3f3f ;
struct edge {
    int to, cap, rev ;
    edge () {}
    edge (int _to, int _cap, int _rev) {to = _to, cap = _cap, rev = _rev;}
} ;
vector<edge> G[maxn] ;
int level[maxn], iter[maxn] ;
void addEdge (int from, int to, int cap) {
    //printf("%d %d %d\n", from, to, cap) ;
    G[from].push_back (edge (to, cap, G[to].size())) ;
    G[to].push_back (edge (from, 0, G[from].size() - 1)) ;
}
void bfs (int s) {
    memset (level, -1, sizeof level) ;
    queue<int> que ;
    que.push (s); level[s] = 0 ;
    while (!que.empty()) {
        int v = que.front(); que.pop() ;
        for (int i = 0; i < G[v].size(); i ++) {
            edge e = G[v][i] ;
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1 ;
                que.push (e.to) ;
            }
        }
    }
}
int dfs (int v, int t, int f) {
    if (v == t) return f ;
    for (int &i = iter[v]; i < G[v].size(); i ++) {
        edge &e = G[v][i] ;
        if (e.cap > 0 && level[e.to] > level[v]) {
            int d = dfs (e.to, t, min (f, e.cap)) ;
            if (d > 0) {
                e.cap -= d ;
                G[e.to][e.rev].cap += d ;
                return d ;
            }
        }
    }
    return 0 ;
}
int maxflow (int s, int t) {
    int flow = 0 ;
    for (;;) {
        bfs (s) ;
        if (level[t] < 0) return flow ;
        memset (iter, 0, sizeof iter) ;
        int f ;
        while ((f = dfs (s, t, INF)) > 0) flow += f ;
    }
}
int n, m ;
vector<P> g[maxn] ;
int dfn[maxn], low[maxn], stk[maxn], num, top, cnt ;
vector<int> dcc[maxn] ;
int color[maxn] ;
void add_Edge (int u, int v, int id) {
    g[u].push_back (P (v, id)) ;
    g[v].push_back (P (u, id)) ;
}
void tarjan (int v, int fa) {
    dfn[v] = low[v] = ++ num ;
    for (int i = 0; i < g[v].size(); i ++) {
        int y = g[v][i].fi, id = g[v][i].se ;
        if (y == fa) continue ;
        if (!dfn[y]) {
            stk[++ top] = id ;
            tarjan (y, v) ;
            low[v] = min (low[v], low[y]) ;
            if (low[y] >= dfn[v]) {
                cnt ++ ;
                while (stk[top] != id) dcc[cnt].push_back (stk[top --]) ;
                dcc[cnt].push_back (stk[top --]) ;
            }
        } else if (dfn[y] < dfn[v]) {
            stk[++ top] = id ;
            low[v] = min (low[v], dfn[y]) ;
        }
    }
}
int main() {
    cin >> n >> m ;
    for (int i = 1; i <= m; i ++) {
        int u, v, c ;
        scanf("%d%d%d", &u, &v, &c) ;
        color[i] = c ;
        add_Edge (u, v, i) ;
    }
    tarjan (1, 0) ;
    int s = 0, t = cnt + m + 1 ;
    for (int i = 1; i <= cnt; i ++) {
        if (dcc[i].size() == 1) addEdge (s, i, 1) ;
        else addEdge (s, i, dcc[i].size() - 1) ;
        for (int j = 0; j < dcc[i].size(); j ++)
            addEdge (i, cnt + color[dcc[i][j]], 1) ;
    }
    for (int i = 1; i <= m; i ++)
        addEdge (cnt + i, t, 1) ;
    printf("%d\n", maxflow (s, t)) ;
    return 0 ;
}