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

题意：给你n个点，m条边（有单向边也有双向边），由于最小割不止一种，求所有最小割种，边数最少的那个割集，输出最少的边数

两个思路：

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;
    cnt=0;
    while (BFS()){
        memset(cur,0,sizeof(cur));
        ll t;
        while((t = DFS(s,MAX)) > 0) max_flow += t;
    }
	return max_flow;
}

int T,case=1;

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

	return 0;
}