Harry Potter and the Forbidden Forest

3

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

Case 1: 3
Case 2: 2
Case 3: 2
分析：题意为求最小割边中边数最小的割的割边数。方法有很多种：
    类型一：跑第一遍最大流，把残余网络中的割边（即剩余流量为0的变）赋权值为1，其余为inf，再一遍最大流即可。
    类型二：通过改变边的权值，想象如果每一条边容量都加1，那么最小割中，边数多的的割加的流量多于边数少的割的流量，那么边数多的就不是割了（流量打了）
           当然不是绝对加一，使边的权值w变为w*（E+1）+1，是最大流%(E+1),此为最小割最小边数，这样防止改变最小割的结果。
    代码示例（类型1）：
    #include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<queue>#define Lh 2000#define Le 2000000#define max 1000000000using namespace std;typedef struct{    int to;    int w;    int next;}node;typedef struct{    int x;    int t;}DEP;node E[Le];DEP fir,nex;int head[Lh],headx[Lh],deep[Lh],cnt;void init(){    memset(head,-1,sizeof(head));    cnt=0;}void add(int a,int b,int c){    E[cnt].to=b;    E[cnt].w=c;    E[cnt].next=head[a];    head[a]=cnt++;    E[cnt].to=a;    E[cnt].w=0;    E[cnt].next=head[b];    head[b]=cnt++;}int min(int x,int y){    return x<y?x:y;}int bfs(int s,int t,int n){    memset(deep,255,sizeof(deep));    queue<DEP>Q;    fir.x=s;    fir.t=0;    deep[s]=0;    Q.push(fir);    while(!Q.empty())    {        fir=Q.front();        Q.pop();        for(int i=head[fir.x];i!=-1;i=E[i].next)        {            nex.x=E[i].to;            nex.t=fir.t+1;            if(deep[nex.x]!=-1||!E[i].w)            continue;            deep[nex.x]=nex.t;            Q.push(nex);        }    }    for(int i=0;i<=n;i++)    headx[i]=head[i];   return deep[t]!=-1;}int dfs(int s,int t,int flow){    if(s==t)    return flow;    int newflow=0;    for(int i=headx[s];i!=-1;i=E[i].next)    {           headx[s]=i;        int to=E[i].to;        int w=E[i].w;        if(!w||deep[to]!=deep[s]+1)        continue;        int temp=dfs(to,t,min(w,flow-newflow));        newflow+=temp;        E[i].w-=temp;        E[i^1].w+=temp;        if(newflow==flow)        break;    }    if(!newflow)deep[s]=0;    return newflow;}int Dinic(int s,int t,int m){    int sum=0;    while(bfs(s,t,m))    {           sum+=dfs(s,t,max);    }    return sum;}int main(){    int a,b,c,d;    int n,m,T;    scanf("%d",&T);    for(int t=1;t<=T;t++)    {        scanf("%d%d",&n,&m);        init();        for(int i=0;i<m;i++)        {            scanf("%d%d%d%d",&a,&b,&c,&d);            add(a,b,c);            if(d)            add(b,a,c);        }        Dinic(0,n-1,n);        for(int i=0;i<=cnt;i+=2)        {          if(!E[i].w)          E[i].w=1;          else          E[i].w=max;        }        printf("Case %d: %d\n",t,Dinic(0,n-1,n));    }    return 0;}