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

作者: wjyyy 分类: 最小割,构造,网络流,解题报告 发布时间: 2018-07-02 08:53

点击量:8

 

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

 

题目描述

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

 

输入输出格式

输入格式:

第一行: 两个整数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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */