$update: 2019.08.30$

题面

求最小割，并且在最小割的情况下求出最少要删去几条边

思路：

最小割

就是后一问不大好求

或许我们要在模板里改比较困难

那么我们就想办法在边上做学问

比如我们可不可以把边的容量全部加1呢？

有人问：这样最小割不就是不一样了吗？

但是细想一下可以发现：其实在加1的情况下，原来的最小割确实变了，但是增大了多少就等于最少要删去的边数

因为对于每条边，容量又多了一个1，在最小割的前提下，肯定是删去越少的边数的情况更优

举个栗子：

上述划去的内容都是有点瑕疵的

比如下图情况，即可将这种做法 $hack$

也就是，把边的容量 $+1$ 之后，会对最小割产生影响

因此我们需要一种对最小割不产生影响，并且可以计算出最小割边数的修改方法

和上述的方法仍有一点相似，可以将边的容量变成一个 $m+1$ 进制数（$m$ 是边数）

十位为原来的容量，个位为 $1$，表示一条边的代价，这样可以一次性求出最小割和最小割的边数，

由于变成 $m+1$ 进制数后，就算边数再多，可不会对最小割产生影响，因为十位决定的是大前提，个位决定的是细节，也就是边数，不会对最小割产生影响

可以这么极端地想，就算每条边都走了，对最小割产生的影响也只能存在于个位，不会进一到十位

最后答案，最小割即为跑 $Dinic$ 得出的结果在 $m+1$ 进制下的十位，边数则为个位

Code：

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define ll long long
#define M 1010
#define N 50
using namespace std;
struct node{
    int to,cap;
    int nxt;
    node(int a,int b):to(a),cap(b){    }
    node(){    }
}b[M<<1];
int head[N],deep[N];
int A,n,m,S,T,t=1;
ll Maxflow;
int read()
{
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s;
}
void add(int x,int y,int cap)
{
    b[++t]=node(y,cap);
    b[t].nxt=head[x];
    head[x]=t;
    b[++t]=node(x,0);
    b[t].nxt=head[y];
    head[y]=t;
    return;
}
bool BFS()
{
    int i,cur;
    int to,cap;
    queue<int>p;
    memset(deep,0,sizeof(deep));
    deep[S]=1;p.push(S);
    while(!p.empty())
    {
        cur=p.front();p.pop();
        for(i=head[cur];i;i=b[i].nxt)
        {
            to=b[i].to;cap=b[i].cap;
            if(cap&&!deep[to])
            {
                deep[to]=deep[cur]+1;
                p.push(to);
                if(to==T)
                    return 1;
            }
        }
    }
    return 0;
}
ll Dinic(int k,ll flow)
{
    if(k==T)
        return flow;
    int i,to,res;
    ll cap,rest=flow;
    for(i=head[k];i&&rest;i=b[i].nxt)
    {
        to=b[i].to;cap=b[i].cap;
        if(cap&&deep[to]==deep[k]+1)
        {
            res=Dinic(to,min(rest,cap));
            if(!res)
                deep[to]=0;
            b[i].cap-=res;
            b[i^1].cap+=res;
            rest-=res;
        }
    }
    return flow-rest;
}
int main()
{
    int i,x,y,cap;
    ll flow;
    n=read();m=read();
    S=1;T=n;A=m+1;
    for(i=1;i<=m;i++)
    {
        x=read();y=read();cap=read();
        add(x,y,cap*A+1);//变成m+1进制数
    }
    while(BFS())
        while((flow=Dinic(S,INF)))
            Maxflow+=flow;
    printf("%lld %lld",Maxflow/A,Maxflow%A);
    return 0;
}

devil.