[USACO Section 4.4]追查坏牛奶Pollutant Control (最小割)

题目链接

Solution

一眼看过去就是最小割,但是要求割边最少的最小的割.

所以要用骚操作...

建边的时候每条边权 \(w = w * (E+1) + 1;\)

那么这样建图跑出来的 \(maxflow\) 为原图 \(maxflow\) 的 \(E+1\) 倍加上割边数量.

割边数量很显然就是 \(maxflow~mod~(E+1)\).

我们很显然不能让割边数量大于模数,所以我们乘上的大数要比原有的边数多.

同时由于 \(maxflow\) 数值确定;

那么割边多的最小割肯定会长一些,所以我们此时跑出来的一定是割边最少的最小割.

为什么是 \(E+1\) ? 因为割边最多 \(E\) 条,所以 \(mod~(E+1)\) 才会没有问题. 其实 \(E+\infty\) 都可以..

Code

#include<bits/stdc++.h>

#define inf 0x3f3f3f3f

#define in(x) x=read()

#define ll long long

using namespace std;

const int mod=6008;

ll cost[mod+10],ans=0;

int to[mod+10],nxt[mod+10],head[mod+10];

int depth[mod+10],cur[mod+10],v[mod+10];

int n,m,tot=1;

int read()

{

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

    while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}

    return f*ret;

}

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

{

	to[++tot]=y;

	cost[tot]=z;

	nxt[tot]=head[x];

	head[x]=tot;

}

bool bfs()

{

	queue<int> q;

    memset(depth,0,sizeof(depth));

    q.push(1);depth[1]=1;

    while(!q.empty())

    {

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

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

        {

            int y=to[i];

            if ((!depth[y])&&cost[i]) depth[y]=depth[x]+1,q.push(y);

        }

    }

    return depth[n]==0?false:true;

}

ll dfs(int x,ll f)

{

    ll w=0,used=0;

    if (x==n) return f;

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

    {

        int y=to[i];

        if (depth[y]==depth[x]+1)

        {

            w=f-used;w=dfs(y,min(cost[i],w));

            cost[i]-=w;cost[i^1]+=w;used+=w;

            if (used==f) return f;

        }

    }

    if (!used) depth[x]=-1;

    return used;

}

int main()

{

    in(n); in(m);

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

    {

        int x,y;ll z;

        in(x),in(y),in(z);

        add(x,y,z*mod+1);add(y,x,0);

    }

    while(bfs())

    {

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

        cur[i]=head[i];

        ans+=dfs(1,inf);

    }

    printf("%lld %lld\n",ans/mod,ans%mod);

    return 0;

}

巴特西

[USACO Section 4.4]追查坏牛奶Pollutant Control (最小割)

题目链接

Solution

Code

最新文章

热门文章