题意：给出$N$个节点$M$条边的有向图，边权为$w$，求其最小割与达到最小割的情况下割掉边数的最小值。$N \leq 32,M \leq 1000,w\leq 2 \times 10^6$
$N \leq 32$emmmm
求最小割直接套EK或者Dinic模板即可，但是如何求最少边数？
考虑将所有边权$w$变为$w \times 1000 + 1$，这样求出的最小割为$All$，则原图的最小割为$\frac{All}{1000}$，而最小割的最小边数为$All mod 1000$。
#include<bits/stdc++.h>
#define ccc 10001
using namespace std;
struct Edge{
long long end , upEd , w;
}Ed[];
] , dep[] , N , cntEd;
inline void addEd(long long a , long long b , long long c){
Ed[cntEd].end = b;
Ed[cntEd].w = c;
Ed[cntEd].upEd = head[a];
head[a] = cntEd++;
}
queue < long long > q;
inline bool bfs(){
while(!q.empty())
q.pop();
memset(dep , , sizeof(dep));
dep[] = ;
q.push();
while(!q.empty()){
long long t = q.front();
q.pop();
; i = Ed[i].upEd)
if(!dep[Ed[i].end] && Ed[i].w){
dep[Ed[i].end] = dep[t] + ;
if(Ed[i].end == N)
;
q.push(Ed[i].end);
}
}
;
}
long long dfs(long long dir , long long minN){
if(dir == N)
return minN;
)
;
;
; i = Ed[i].upEd)
&& Ed[i].w){
long long t = dfs(Ed[i].end , min(minN , Ed[i].w));
sum += t;
Ed[i].w -= t;
Ed[i ^ ].w += t;
minN -= t;
}
return sum;
}
int main(){
memset(head , - , sizeof(head));
, cnt = ;
cin >> N >> M;
while(M--){
long long a , b , c;
cin >> a >> b >> c;
addEd(a , b , c * ccc + );
addEd(b , a , );
}
while(bfs())
ans += dfs( , 1ll<<);
cout << ans / ccc << ' ' << ans % ccc;
;
}