题目链接：https://cn.vjudge.net/problem/HDU-6214

题意：给你n个点，m条边，源点s，汇点t，让你求最小割的最少变数

思路和我上一篇博客HDU-3987一样

两个思路：

1、先跑一遍最大流，然后让饱和的边的容量置为1，不饱和的置为INF，再跑一遍最大流即可

2、让每条边的边权乘上一个大于边数的数再加1，然后跑一边最大流，最后输出结果%乘的那个数即可

 

#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = (1ll << 31) - 1;
const int mavn = 4e5+5;
const int maxn = 1e5+5;
#define ll long long
struct Edge{
    int to;
    ll dis;
    int rev;
    Edge(){}
    Edge(int to,ll d,int c):to(to),dis(d),rev(c){}
} ;
vector<Edge> v[maxn];
int cur[mavn];
int n, m, s, t;
struct node {
	int u,v,d;
	ll c;
	node(){}
	node(int a,int b,ll c,int d):u(a),v(b),c(c),d(d){}
}pos[mavn];
void addEdge(int from, int to, ll dis){
    v[from].push_back(Edge(to, dis,v[to].size()));
    v[to].push_back(Edge(from, 0,v[from].size()-1));
}

int d[mavn],cnt;

ll DFS(int u, ll flow){
    if (u == t || !flow) return flow;
    ll ans = 0, tmp_flow;
    for (int& i = cur[u]; i < v[u].size(); i++){
        int to = v[u][i].to;
        if (d[to] == d[u] + 1 && v[u][i].dis > 0){
            tmp_flow = DFS(to, min(flow, v[u][i].dis));
            if(tmp_flow > 0) {
		flow -= tmp_flow;
		v[u][i].dis -= tmp_flow;
		ans += tmp_flow;
		v[to][v[u][i].rev].dis += tmp_flow;
		if (!flow)
                    break;
            }
        }
    }
    if (!ans) d[u] = -1;
    return ans;
}

bool BFS(){
    memset(d,-1,sizeof(d));
    queue<int> que;
    que.push(s);
    d[s] = 0;
    int u, _new;
    while (!que.empty()){
        u = que.front();
        que.pop();
        for (int i = 0; i < v[u].size(); i++){
            _new = v[u][i].to;
            if (d[_new] == -1 && v[u][i].dis > 0){
                d[_new] = d[u] + 1;
                que.push(_new);
            }
        }
    }
    return (d[t] != -1);
}

ll  dinic(){
    ll max_flow = 0;
    while (BFS()){
        memset(cur,0,sizeof(cur));
        ll tt;
        while((tt = DFS(s,MAX)) > 0) max_flow += tt;
    }
    return max_flow;
}

int T;

int main(){
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        scanf("%d%d",&s,&t);
        for(int i=1 ; i<=m ; ++i){
            int a,b;ll c;
	    scanf("%d %d %lld",&a,&b,&c);
    	    addEdge(a,b,c*(m+1)+1);
	}
	printf("%d\n",dinic()%(m+1));
        for(int i=0;i<=n;i++) v[i].clear();
    }
    return 0;
}