[USACO4.4]追查坏牛奶Pollutant Control

Solution:

第一问很好解决，根据网络流：最大流=最小割定理，我们可以轻松求出。

至于第二问，我们不妨把每一条边乘上一个大于1000的数再加上1。

这样的话，对于最小割，显然就是求出来的\(maxflow/W\)(W为乘上的数)。

而对于第二问，则是\(maxflow\,\,mod \,\,W\)，因为每割去一条边，它就会加上1

Code:

#include<bits/stdc++.h>

#define N 3001

#define inf 1926081700

#define int long long

using namespace std;

int n,m,cnt=1;

int S=1,T,head[N];

struct Edge{int nxt,to,v;}edge[N];

void ins(int x,int y,int z){

    edge[++cnt].nxt=head[x];

    edge[cnt].to=y;edge[cnt].v=z;

    head[x]=cnt;

}

namespace Network_Flow{

    queue<int> q;

    int delta,dep[N];

    int bfs(){

        delta=inf;

        memset(dep,0,sizeof(dep));

        q.push(S);dep[S]=1;

        while(!q.empty()){

            int x=q.front();q.pop();

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

            if(!dep[edge[i].to]&&edge[i].v){

                dep[edge[i].to]=dep[x]+1;

                delta=min(delta,edge[i].v);

                q.push(edge[i].to);

            }

        }

        return dep[T];

    }

    int dfs(int x,int rest){

        if(x==T||rest<=0) return rest;

        int flow=0;

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

            int y=edge[i].to,v=edge[i].v;

            if(v&&dep[y]==dep[x]+1){

                int now=dfs(y,min(rest,v));

                edge[i].v-=now;

                edge[i^1].v+=now;

                flow+=now;rest-=now;

                if(rest<=0) break;

            }

        }

        return flow;

    }

    void dinic(){

        int maxflow=0;

        while(bfs()) maxflow+=dfs(S,inf);

        int ans1=maxflow,ans2=maxflow;

        printf("%lld %lld\n",ans1/N,ans2%N);

    }

}

int read(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}

    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();};

    return x*f;

}

signed main(){

    n=read(),m=read();T=n;

    for(int x,y,z,i=1;i<=m;i++){

        x=read(),y=read(),z=read();

        ins(x,y,z*N+1);ins(y,x,0);

    }

    using namespace Network_Flow;

    dinic();

    return 0;

}