view code//hdu 3987 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; typedef long long ll; const ll INF = 1LL<<59; const ll E = 100001; const int N = 1010; int _, n, m, pre[N], cur[N], d[N], s, t; bool vis[N]; struct edge { int u, v; ll cap, flow; int next; edge() {} edge(int u, int v, ll w, ll f, int p):u(u),v(v),cap(w),flow(f),next(p) {} }e[N*400]; int ecnt; void addedge(int u, int v, int w) { e[ecnt] = edge(u, v, w*E+1, 0, pre[u]); pre[u] = ecnt++; e[ecnt] = edge(v, u, 0, 0, pre[v]); pre[v] = ecnt++; } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int >q; q.push(s); d[s] = 0; vis[s] = 1; while(!q.empty()) { int x = q.front(); q.pop(); for(int i=pre[x]; ~i; i = e[i].next) { int v =e[i].v; if(!vis[v] && e[i].cap>e[i].flow) { d[v] = d[x] + 1; vis[v] = 1; q.push(v); } } } return vis[t]; } ll DFS(int x, ll c) { if(x==t || c==0) return c; ll flow = 0, f; for(int &i = cur[x]; ~i; i=e[i].next) { int v = e[i].v; if(d[x] + 1 == d[v] && (f=DFS(v, min(c, e[i].cap-e[i].flow)))>0) { e[i].flow += f; e[i^1].flow -= f; flow += f; c -= f; if(c==0) break; } } return flow; } ll Maxflow() { s = 0, t = n-1; ll flow = 0; while(BFS()) { for(int i=s; i<=t; i++) cur[i] = pre[i]; flow += DFS(s, INF); } return flow; } void solve() { scanf("%d%d", &n, &m); int u, v, w, flag; memset(pre, -1, sizeof(pre)); ecnt = 0; for(int i=0; i<m; i++) { scanf("%d%d%d%d", &u, &v, &w, &flag); addedge(u, v, w); if(flag) addedge(v, u, w); } static int cas=1; printf("Case %d: ", cas++); cout<<Maxflow()%E<<endl; } int main() { // freopen("in.txt", "r", stdin); cin>>_; while(_--) solve(); return 0; } /* 题意： 求最小割，但因为最小割是不唯一的，题目要求得到最小割的条件下，使得割边最少，输出最少割边数 思路： 有两种做法，但本质是一样的 第一种： 建边的时候每条边权 w = w * (E + 1) + 1; 这样得到最大流 maxflow / (E + 1) ，最少割边数 maxflow % (E + 1) 道理很简单，如果原先两类割边都是最小割，那么求出的最大流相等 但边权变换后只有边数小的才是最小割了 乘（E+1）是为了保证边数叠加后依然是余数，不至于影响求最小割的结果 第二种： 建图，得到最大流后，图中边若满流，说明该边是最小割上的边 再建图，原则：满流的边改为容量为 1 的边，未满流的边改为容量 INF 的边，然后最大流即答案 */