洛谷 P1344 [USACO4.4]追查坏牛奶Pollutant Control 题解【网络流】【最小割】【构造】

点击量：178

   又是一个巧妙的最小割建模题。

目录

题目描述

你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

 

输入输出格式

输入格式：

第一行: 两个整数N(2<=N<=32)、M(0<=M<=1000), N表示仓库的数目，M表示运输卡车的数量。仓库1代 表发货工厂，仓库N代表有三聚氰胺的牛奶要发往的零售商。 第2..M+1行: 每行3个整数Si,Ei,Ci。其中Si,Ei表示这 辆卡车的出发仓库，目的仓库。Ci(0 <= C i <= 2,000,000) 表示让这辆卡车停止运输的损失。

 

输出格式：

两个整数C、T：C表示最小的损失，T表示在损失最小的前提下，最少要停止的卡车数。

 

输入输出样例

输入样例#1：

4 5

1 3 100

3 2 50

2 4 60

1 2 40

2 3 80

输出样例#1：

60 1

   很容易看出来，我们要让所有卡车都不跑，首先要降低损失，如果建模为费用流，那么这里的最大流的费用不一定最小。因此我们可以建立最小割模型，因为要使损失最小，就要用最小割。

   而题目要求保证损失最小的情况下，再看停的卡车数量最少。这样看上去两者有依附关系，又会想到费用流，同样因为先决顺序也不行。我们可以先跑一遍最小割，此时边权为卡车的损失。这样我们求出来的就是花费最少的钱使得整张图被分成两半，第一问就这样做出来了。第二问要求在第一问的条件下，那么求第一问时要停的卡车在第二问可能不停了，因为如果只停一辆较高花费的损失可能和停两辆较低花费的一样多。

   因此我们在保证图左右连通的前提下，把原本满流的边置为1，原本不满流的边置为inf，因为原本满流的边是可能被截掉的，而原本不满流的边切掉是不符合题意的，保证了切掉满流的边贡献为1，并给反边都置0。

   这里的两次其实都是最小割的思想，因为第一次是使花费最小，第二次是使停车最少。第二问的图在第一问的基础上修改，就保证了第一问成立并第二问正确。因此我们跑两遍最小割就可以了。

Code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
struct edge
{
    int n,v;
    int nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[2005];
int cnt=-1,head[50];
void add(int from,int to,int v)
{
    e[++cnt]=edge(to,v,head[from]);
    head[from]=cnt;
    e[++cnt]=edge(from,0,head[to]);
    head[to]=cnt;
}
int n,m;
int d[50],gap[50];
void bfs()
{
    int q[1000],l=0,r=0;
    q[++r]=n;
    while(l<r)
    {
        int k=q[++l];
        for(int i=head[k];~i;i=e[i].nxt)
            if(e[i].v&&d[e[i].n]==0)
            {
                d[e[i].n]=d[k]+1;
                gap[d[e[i].n]]++;
                q[++r]=i;
            }
    }
}
int pre[50],sum=0;
int cur[50];

void isap()
{
    for(int i=1;i<=n;i++)
        cur[i]=head[i];
    memset(d,0,sizeof(d));
    memset(pre,-1,sizeof(pre));
    memset(gap,0,sizeof(gap));
    bfs();
    gap[0]=999;
    int s=1;
    while(d[1]<n)
    {
        //printf("1");
        if(s==n)
        {
            int p=pre[n];
            int minn=99999999;
            while(~p)
            {
                minn=minn<e[p].v?minn:e[p].v;
                p=pre[e[p^1].n];
            }
            sum+=minn;
            p=pre[n];
            while(~p)
            {
                e[p].v-=minn;
                e[p^1].v+=minn;
                p=pre[e[p^1].n];
            }
            s=1;
        }
        int flag=0;
        for(int i=cur[s];~i;i=e[i].nxt)
            if(e[i].v&&d[s]==d[e[i].n]+1)
            {
                flag=1;
                cur[s]=e[i].nxt;
                s=e[i].n;
                pre[s]=i;
                break;
            }
        if(flag==0)
        {
            int tmp=d[s];
            d[s]=2*n;
            for(int i=head[s];~i;i=e[i].nxt)
                if(e[i].v)
                    d[s]=d[s]<d[e[i].n]+1?d[s]:d[e[i].n]+1;
            gap[tmp]--;
            gap[d[s]]++;
            if(gap[tmp]==0)
                return;
            cur[s]=head[s];
            if(s!=1)
                s=e[pre[s]^1].n;
        }
    }
    return;
}
int main()
{
    //freopen("data.in","r",stdin);
    int u,v,w;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);//第一次建图
        add(u,v,w);
    }
    isap();
    printf("%d ",sum);
    for(int i=0;i<=cnt;i+=2)
    {
        if(e[i].v==0)//第二次改图
            e[i].v=1;
        else
            e[i].v=0x3fffffff;
        e[i+1].v=0;
    }
    sum=0;
    isap();
    printf("%d\n",sum);
    return 0;
}