Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2089 Accepted Submission(s): 702
题目链接：HDU 3987
题意就是在最小割的前提下求最少的割边数，把非0流量边放大，设$maxcap$为可能出现的最大流量值（最好为10的倍数方便计算），变成$cap = cap * maxcap + 1$，0流量的肯定是不能放大的，否则出现1个流量了。
这样一来不会改变边的大小关系，但是流量蕴含了边数，求得的最小割一定由最少割边数构成，最后求得的最小割就是$maxflow / maxcap$，最小割边数就是$maxflow$ % $maxcap$。
代码：
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1010;
const int M = 200010;
struct edge
{
int to, nxt;
LL cap;
edge() {}
edge(int _to, int _nxt, LL _cap): to(_to), nxt(_nxt), cap(_cap) {}
};
edge E[M << 1];
int head[N], tot, d[N];
void init()
{
CLR(head, -1);
tot = 0;
}
inline void add(int s, int t, LL cap)
{
E[tot] = edge(t, head[s], cap);
head[s] = tot++;
E[tot] = edge(s, head[t], 0LL);
head[t] = tot++;
}
int bfs(int s, int t)
{
CLR(d, -1);
d[s] = 0;
queue<int>Q;
Q.push(s);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = head[u]; ~i; i = E[i].nxt)
{
int v = E[i].to;
if (d[v] == -1 && E[i].cap > 0LL)
{
d[v] = d[u] + 1;
if (v == t)
return 1;
Q.push(v);
}
}
}
return ~d[t];
}
LL dfs(int s, int t, LL f)
{
if (s == t || !f)
return f;
LL ret = 0LL;
for (int i = head[s]; ~i; i = E[i].nxt)
{
int v = E[i].to;
if (d[v] == d[s] + 1 && E[i].cap > 0LL)
{
LL df = dfs(v, t, min<LL>(f, E[i].cap));
if (df > 0LL)
{
E[i].cap -= df;
E[i ^ 1].cap += df;
ret += df;
f -= df;
if (!f)
break ;
}
}
}
if (!ret)
d[s] = -1;
return ret;
}
LL dinic(int s, int t)
{
LL ret = 0LL;
while (bfs(s, t))
ret += dfs(s, t, 0x3f3f3f3f3f3f3f3f);
return ret;
}
int main(void)
{
int tcase;
scanf("%d", &tcase);
for (int q = 1; q <= tcase; ++q)
{
init();
int n, m, i;
scanf("%d%d", &n, &m);
for (i = 0; i < m; ++i)
{
int u, v, d;
LL c;
scanf("%d%d%I64d%d", &u, &v, &c, &d);
if (c)
c = c * 1000000LL + 1LL;
add(u, v, c);
if (d)
add(v, u, c);
}
printf("Case %d: %I64d\n", q, dinic(0, n - 1) % 1000000LL);
}
return 0;
}
HDU 3987 Harry Potter and the Forbidden Forest（边权放大法+最小割）
原文：http://www.cnblogs.com/Blackops/p/6385713.html