題意: 一個人要從起點 0 到達 n-1 n個點 m條路 ，我們求最少破壞路的條數使無法 從起點到達終點。題意很明顯 ，求最小割條數最少，由於最小割流量雖然固定，但是其條數卻不固定，可以破壞3條路，也可以破壞4條路，他們總流量相同才會出現這種情況。
題解：由於上述的情況，他們總流量相同但是條數不同，現在我們需要改變邊的容量使得條數少邊才是最小割，條數多的將不會是最小割。
官方題解有兩種 ，我選擇的是在殘余網絡中進行擴充流的操作，使的兩個最小割不同，殘余網絡中，我進行所有邊流量加1的操作，在跑一遍最大流可以得出最小割的最小條數
還有一種方法是在跑最大流之前擴充流量 ，然後對跑出的最小割進行處理得出最小割的最小條數。
代碼
#include
#include
#include
#define INF 0x3f3f3f3f
#define N 1005
using namespace std;
int list[N], listt[N], deep[N], tot;
struct Node
{
int date, next, value;
}cun[2000005];
struct b
{
int x, t;
}old, xin;
void add(int a, int b, int c)
{
cun[++tot].date = b;
cun[tot].value = c;
cun[tot].next = list[a];
list[a] = tot;
cun[++tot].date = a;
cun[tot].value = 0;
cun[tot].next = list[b];
list[b] = tot;
}
int bfs(int s, int t, int n)
{
queue p;
old.x = s;
old.t = 0;
p.push(old);
memset(deep,255,sizeof(deep));
deep[s] = 0;
while(!p.empty())
{
old = p.front();
p.pop();
for(int i = list[old.x]; i; i = cun[i].next)
{
int date = cun[i].date;
int value = cun[i].value;
if(value == 0 || deep[date] != -1) continue;
xin.x = date;
xin.t = old.t + 1;
deep[date] = xin.t;
p.push(xin);
}
}
for(int i = 0; i <= n; i++)
{
listt[i] = list[i];
}
return deep[t] != -1;
}
int minn(int a, int b)
{
if(a < b) return a;
return b;
}
int dfs(int s, int t, int min)
{
if(s == t) return min;
int neww = 0;
for(int i = listt[s]; i; i = cun[i].next)
{
listt[s] = i;
int date = cun[i].date;
int value = cun[i].value;
if(value == 0 || deep[date] != deep[s] + 1) continue;
int m = dfs(date, t, minn(value, min - neww));
neww += m;
cun[i].value -= m;
cun[i^1].value += m;
if(neww == min) break;
}
if(neww == 0) deep[s] = 0;
return neww;
}
int dinic(int s, int t, int n)
{
int num = 0;
while(bfs(s, t, n))
{
num += dfs(s, t, INF);
}
return num;
}
int main()
{
int n, m, a, b, c, flag, T, flagg = 1;
scanf("%d", &T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(list,0,sizeof(list));
tot = 1;
for(int i = 1; i <= m; i++)
{
scanf("%d %d %d %d", &a, &b, &c, &flag);
add(a+1, b+1, c);
if(flag)
add(b+1, a+1, c);
}
int k = dinic(1, n, n+5);
for(int i = 2; i <= tot; i += 2)
{
cun[i].value ++;
}
k = dinic(1, n, n+5);
printf("Case %d: %d\n", flagg++, k);
}
}
