洛谷 1344 [USACO4.4]追查坏牛奶Pollutant Control——最大流

题目：https://www.luogu.org/problemnew/show/P1344

那个边数的限制，只要把边权乘1001再+1即可。乘1001是因为有1000条边，这样流量小的不会因为边数多而被认为不优。不是乘1000是为了/1001和%1001取出答案,1000的话略有冲突。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=,M=;

const ll INF=0x3f3f3f3f3f3f3f3f;

int n,m,hd[N],cur[N],xnt=,dfn[N];

int q[N],he,tl;

ll mxflow;

struct Ed{

    int nxt,to,cap;

    Ed(int n=,int t=,int c=):nxt(n),to(t),cap(c) {}

}ed[M<<];

void add(int x,int y,int z)

{

    ed[++xnt]=Ed(hd[x],y,z);hd[x]=xnt;

    ed[++xnt]=Ed(hd[y],x,);hd[y]=xnt;

}

bool bfs()

{

    memset(dfn,,sizeof dfn);

    dfn[]=; he=tl=; q[++tl]=;

    while(he<tl)

    {

        int k=q[++he];

        for(int i=hd[k],v;i;i=ed[i].nxt)

            if(ed[i].cap&&!dfn[v=ed[i].to])

                dfn[v]=dfn[k]+,q[++tl]=v;

    }

    return dfn[n];

}

ll dinic(int cr,ll flow)

{

    if(cr==n) return flow;

    ll use=;

    for(int &i=cur[cr],v;i;i=ed[i].nxt)

        if(dfn[v=ed[i].to]==dfn[cr]+&&ed[i].cap)

        {

            ll tmp=dinic(v,min(flow-use,(ll)ed[i].cap));

            if(!tmp) dfn[v]=;

            ed[i].cap-=tmp; ed[i^].cap+=tmp;

            use+=tmp; if(use==flow) return use;

        }

    return use;

}

int main()

{

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

    for(int i=,u,v,z;i<=m;i++)

    {

        scanf("%d%d%d",&u,&v,&z);

        add(u,v,z*+);

    }

    while(bfs())

    {

        memcpy(cur,hd,sizeof hd);

        mxflow+=dinic(,INF);

    }

    printf("%lld %lld\n",mxflow/,mxflow%);

    return ;

}