Dinic+maxflow
题意：找这样一种边的个数，就是增加该边的容量，可以使得最大流变大
思路：求maxflow，再枚举流量为0的边，增加容量，看是否能找到增广路径。
/*
Dinic+maxflow
题意：找这样一种边的个数，就是增加该边的容量，可以使得最大流变大
思路：求maxflow，再枚举流量为0的边，增加容量，看是否能找到增广路径。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = ;
const int maxm = ;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps = 1e-; struct Edge{
int u,v,next,val;
bool flag;
}edge[ maxm<< ];
int cnt,head[ maxn ];
int vis[ maxn ];
int lev[ maxn ];
int q[ maxn<< ]; void init(){
cnt = ;
memset( head,-,sizeof( head ) );
}
void addedge( int a,int b,int c ){
edge[ cnt ].u = a;
edge[ cnt ].v = b;
edge[ cnt ].val = c;
edge[ cnt ].next = head[ a ];
if( cnt%== ) edge[ cnt ].flag = true;
else edge[ cnt ].flag = false;
head[ a ] = cnt ++;
} bool bfs( int n,int start,int end ){
int head2 = ,tail2 = ;
q[ tail2++ ] = start;
memset( lev,-,sizeof( lev ) );
lev[ start ] = ;
while( head2<tail2 ){
int u = q[ head2++ ];
for( int i=head[u];i!=-;i=edge[i].next ){
int v = edge[i].v;
if( edge[i].val>&&lev[v]==- ){
lev[v] = lev[u]+;
q[ tail2++ ] = v;
}
}
}
if( lev[ end ]==- ) return false;
else return true;
} int Dinic( int n,int start,int end ){
int maxflow = ;
while( true ){
if( bfs(n,start,end )==false ) break;
int id = start;
int tail = ;
while( true ){
if( id==end ){
int flow = inf;
int flag = -;
for( int i=;i<tail;i++ ){
if( edge[ q[i] ].val<flow ){
flow = edge[ q[i] ].val ;
flag = i;
}
}
for( int i=;i<tail;i++ ){
edge[ q[i] ].val -= flow;
edge[ q[i]^ ].val += flow;
}
if( flag!=- ){
maxflow += flow;
tail = flag;
id = edge[ q[flag] ].u;
}
else
return inf;
}
id = head[ id ];
while( id!=- ){
if( edge[id].val>&&lev[edge[id].u]+==lev[edge[id].v] ){
break;
}
id = edge[ id ].next;
}
if( id!=- ){
q[ tail++ ] = id;
id = edge[ id ].v;
}
else{
if( tail== ) break;
lev[ edge[q[tail-]].v ] = -;
id = edge[ q[--tail] ].u;
}
}
}
return maxflow;
} int main(){
int n,m;
while( scanf("%d%d",&n,&m)== ){
init();
int a,b,c;
int start = ;
int end = n-;
for( int i=;i<m;i++ ){
scanf("%d%d%d",&a,&b,&c);
addedge( a,b,c );
addedge( b,a, );
}
Dinic( n,start,end );
int ans = ;
for( int i=;i<cnt;i++ ){
if( edge[i].val==&&edge[i].flag==true ){
edge[i].val ++ ;
if( bfs( n,start,end )==true ){
ans ++ ;
}
edge[i].val -- ;
}
}
printf("%d\n",ans);
}
return ;
}