luogu 1344

首先题意就是裸的最小割啦

然后考虑如何统计边数

这里有一个trick：

我们设定一个大于$m$的阈值，对于每条边的边权我们乘这个阈值+1后跑最小割，得到的答案除以阈值就是真正的最小割，取模阈值后就是最少割掉的边数

为什么？

我们考虑：设原来的最小割割掉的边权为$v_{1},v_{2}...v_{n}$，那么乘阈值+1后割掉的边权就是$v_{1}*lim+1,v_{2}*lim+1...v_{n}*lim+1$

也就是$lim(v_{1}+v_{2}+...+v_{n})+n$

注意到$lim$大于边权，因此我们直接跑出最小割分解就是答案

而且显然，加一不会影响最小割的正确性

贴代码：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ll long long

using namespace std;

const ll lim=5000;

const ll inf=0x3f3f3f3f3f3f3f3fll;

struct Edge

{

    int nxt;

    int to;

    ll val;

}edge[2005];

int head[50];

int dis[50];

int cur[50];

int cnt=1;

int n,m;

void add(int l,int r,ll w)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    edge[cnt].val=w;

    head[l]=cnt++;

}

void dadd(int l,int r,ll w)

{

    add(l,r,w),add(r,l,0);

}

int ide(int x)

{

    return x&1?x+1:x-1;

}

bool bfs()

{

    memcpy(cur,head,sizeof(head));

    memset(dis,0,sizeof(dis));

    dis[1]=1;

    queue <int> M;

    M.push(1);

    while(!M.empty())

    {

        int u=M.front();

        M.pop();

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int to=edge[i].to;

            if(!dis[to]&&edge[i].val)dis[to]=dis[u]+1,M.push(to);

        }

    }

    return dis[n];

}

ll dfs(int x,ll lim)

{

    if(x==n)return lim;

    ll ret=0;

    for(int i=cur[x];i;i=edge[i].nxt)

    {

        cur[x]=i;

        int to=edge[i].to;

        if(edge[i].val&&dis[to]==dis[x]+1)

        {

            ll temp=dfs(to,min(lim,edge[i].val));

            if(temp)

            {

                ret+=temp;

                lim-=temp;

                edge[i].val-=temp;

                edge[ide(i)].val+=temp;

                if(!lim)return ret;

            }

        }

    }

    return ret;

}

ll dinic()

{

    ll ans=0;

    while(bfs())ans+=dfs(1,inf);

    return ans;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        ll z;

        scanf("%d%d%lld",&x,&y,&z);

        z=z*lim+1;

        dadd(x,y,z);

    }

    ll s=dinic();

    printf("%lld %lld\n",s/lim,s%lim);

    return 0;

}

luogu 1344的相关教程结束。