1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int maxn = 105;
const int maxm = maxn*maxn*2;
const int INF = 1e9+1;
struct Edge{
int from,to,next,w,cap,flow;
Edge(int from = 0,int to = 0,int w = 0):from(from),to(to),w(w){}
bool operator < (const Edge & X)const{
return w < X.w;
}
}edge[maxm],edge2[maxm];
int head[maxn],deep[maxn],vis[maxn],cur[maxn];
int n,m,cnt;
void addedge(int from,int to,int cap,int flow){
edge[cnt].from = from;
edge[cnt].to = to;
edge[cnt].cap = cap;
edge[cnt].flow = flow;
edge[cnt].next = head[from];
head[from] = cnt++;
}
bool BFS(int s,int t){
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;i++)cur[i] = head[i];
queue<int>q;
q.push(s);
vis[s] = 1;
deep[s] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = head[u];~i;i = edge[i].next){
int v = edge[i].to;
if(!vis[v] and edge[i].cap > edge[i].flow){
vis[v] = 1;
deep[v] = deep[u] + 1;
q.push(v);
}
}
}
return vis[t];
}
int DFS(int u,int t,int approve){
if(u == t or approve == 0)return approve;
int flow = 0,delta = 0;
for(int i = cur[u];~i;i = edge[i].next){
cur[u] = i;
int v = edge[i].to;
if(deep[u] + 1 == deep[v] and (delta = DFS(v,t,min(approve,edge[i].cap - edge[i].flow))) > 0){
edge[i].flow += delta;
edge[i^1].flow -= delta;
flow += delta;approve -= delta;
if(!approve)break;
}
}
return flow;
}
int Dinic(int s,int t){
int flow = 0;
while(BFS(s,t)){
flow += DFS(s,t,INF);
}
return flow;
}
signed main(){
ios::sync_with_stdio(0);
memset(head,-1,sizeof(head));
cin.tie(0);
cin >> n >> m;
for(int i = 1;i <= m;i++){
int f,t,w;
cin >> f >> t >> w;
edge2[i] = Edge(f,t,w);
}
sort(edge2+1,edge2+m+1);
int ans = 0;
for(int i = 1;i <= m;i++){
cnt = 0;
for(int j = 1;j <= n;j++)head[j] = -1,deep[j] = 0;
int s = edge2[i].from,t = edge2[i].to;
for(int j = 1;j < i;j++)if(edge2[j].w < edge2[i].w){
int f = edge2[j].from,t = edge2[j].to;
addedge(f,t,1,0);
addedge(t,f,0,0);
addedge(t,f,1,0);
addedge(f,t,0,0);
}
ans += Dinic(s,t);
}
cout << ans;
return 0;
}
|