思路：

点双联通分量+最大流

用tarjan求出每个点双联通分量

对于大小大于1的点双联通分量，它就是个环，那么源点和这个环相连，

容量为环的大小减一，这个环和环上的颜色连边，容量为一；

对于大小为1的点双连通分量，它只有一条边，那么源点和这个分量连边，

分量和边上颜色连边，容量都为1

然后所有颜色和汇点连边，容量为1

最后跑一遍最大流就可以了

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
     
      using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
      
       #define pli pair
       
        #define pii pair
        
         #define piii pair
         
          #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e4 + 5, M = 4e4 + 25;const int INF = 0x7f7f7f7f;vector
          
            G[N];vector
           
             bcc[N*2];int color[N*2];int low[N], dfn[N], stk[N*2], tot = 0, top = 0, cnt = 0;int level[M], iter[M];struct edge { int to, w, rev;};vector
            
             g[M];void add_edge(int u, int v, int w) { g[u].pb(edge{v, w, g[v].size()}); g[v].pb(edge{u, 0, g[u].size()-1});}void bfs(int s) { mem(level, -1); queue
             
              q; level[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < g[u].size(); i++) { edge e = g[u][i]; if(e.w > 0 && level[e.to] < 0) { level[e.to] = level[u] + 1; q.push(e.to); } } }}int dfs(int u, int t, int f) { if(u == t ) return f; for (int &i = iter[u]; i < g[u].size(); i++) { edge &e = g[u][i]; if(e.w > 0 && level[u] < level[e.to]) { int d = dfs(e.to, t, min(f, e.w)); if(d > 0) { e.w -= d; g[e.to][e.rev].w +=d; return d; } } } return 0;}int max_flow(int s, int t) { int flow = 0; while(true) { bfs(s); if(level[t] < 0) return flow; int f; mem(iter, 0); while ((f = dfs(s, t, INF)) > 0) { flow += f; } }}void tarjan(int u, int fa) { low[u] = dfn[u] = ++tot; for (pii p : G[u]) { int v = p.fi; if(v == fa) continue; if(!dfn[v]) { stk[++top] = p.se; tarjan(v, u); low[u] = min(low[u], low[v]); if(low[v] >= dfn[u]) { cnt++; while(stk[top] != p.se) bcc[cnt].pb(stk[top--]); bcc[cnt].pb(stk[top--]); } } else if(dfn[v] < dfn[u]) { stk[++top] = p.se; low[u] = min(low[u], dfn[v]); } }}int main() { int n, m, u, v, c; scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d %d %d", &u, &v, &color[i]); G[u].pb(pii{v, i}); G[v].pb(pii{u, i}); } tarjan(1, 1); int s = 0, t = cnt+m+1; for (int i = 1; i <= cnt; i++) { if(bcc[i].size() == 1)add_edge(s, i, 1); else add_edge(s, i, bcc[i].size()-1); } for (int i = 1; i <= cnt; i++) { for (int j : bcc[i]) { add_edge(i, cnt+color[j], 1); } } for (int i = 1; i <= m; i++) add_edge(cnt+i, t, 1); printf("%d\n", max_flow(s, t)); return 0;}