题意：

给定n个点m条边(点标从0开始)

下面m行 u v d(边权) k(k=0表示单向，1表示双向)

问：

把0 和 n-1点断开 使得0点无法到达n-1点 需要删去多少条边（删边的花费为边权) 问在最小花费情况下，输出要删的边数

思路：

最小割裸题，以0为源点，n-1为汇点，边权改为 w* E(E>最大的边权) +1

最后最大流%E，就可以得到边数。

注意用 __int64

#include <iostream>
#include <string.h>
#include<stdio.h>
#include<queue>
using namespace std;
#define ll __int64
#define inf 1152921504606846976

#define N 1005
#define M 100010
//N为点数 M为边数

struct Edge{
	int from, to;ll cap;int nex;
}edge[M*8];//注意这个一定要够大 不然会re 还有反向弧

int head[N], edgenum;
void addedge(int u, int v, ll cap){
	Edge E = { u, v, cap, head[u]};
	edge[ edgenum ] = E;
	head[u] = edgenum ++;

	Edge E2= { v, u, 0,   head[v]};
	edge[ edgenum ] = E2;
	head[v] = edgenum ++;
}
int sign[N], s, t;
bool BFS(int from, int to){
	memset(sign, -1, sizeof(sign));
	sign[from] = 0;

	queue<int>q;
	q.push(from);
	while( !q.empty() ){
		int u = q.front(); q.pop();
		for(int i = head[u]; i!=-1; i = edge[i].nex)
		{
			int v = edge[i].to;
			if(sign[v]==-1 && edge[i].cap)
			{
				sign[v] = sign[u] + 1, q.push(v);
				if(sign[to] != -1)return true;
			}
		}
	}
	return false;
}
int Stack[M*4], top, cur[M*4];
ll dinic(){

	ll ans = 0;
	while( BFS(s, t) )
	{
		memcpy(cur, head, sizeof(head));
		int u = s;		top = 0;
		while(1)
		{
			if(u == t)
			{
				ll flow = inf;int loc;//loc 表示 Stack 中 cap 最小的边
				for(int i = 0; i < top; i++)
					if(flow > edge[ Stack[i] ].cap)
					{
						flow = edge[Stack[i]].cap;
						loc = i;
					}

					for(int i = 0; i < top; i++)
					{
						edge[ Stack[i] ].cap -= flow;
						edge[Stack[i]^1].cap += flow;
					}
					ans += flow;
					top = loc;
					u = edge[Stack[top]].from;
			}
			for(int i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标
				if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;
			if(cur[u] != -1)
			{
				Stack[top++] = cur[u];
				u = edge[ cur[u] ].to;
			}
			else
			{
				if( top == 0 )break;
				sign[u] = -1;
				u = edge[ Stack[--top] ].from;
			}
		}
	}
	return ans;
}

int main() {
	int n, m, T, Cas = 1;scanf("%d",&T);
	int u, v, k;ll d;
	while (T--) 
	{
		scanf("%d %d", &n, &m);
		memset(head, -1, sizeof(head));
		ll E = 100001;
		while(m--)
		{
			scanf("%d %d %I64d %d",&u, &v, &d, &k); d*=E; d++;
			addedge(u, v, d); if(k) addedge(v, u, d);
		}
		s = 0, t = n-1;
		printf("Case %d: %I64d\n", Cas++, dinic()%E);
	}
	return 0;
}

/*
99
4 5
0 1 3 0
0 2 1 0
1 2 1 1
1 3 1 1
2 3 3 1

6 7
0 1 1 0
0 2 1 0
0 3 1 0
1 4 1 0
2 4 1 0
3 5 1 0
4 5 2 0

3 6
0 1 1 0
0 1 2 0
1 1 1 1
1 2 1 0
1 2 1 0
2 1 1 1

*/

HDU 3987 求断开两点最小花费下的边数 最小割