POJ 3680 Intervals 最小费用最大流（MCMF算法）

题意：给出 n ,k 表示接下来给你 n 段开区间，每段区间都有它的权值，问选出一些区间，使它的权值最大，并且在实轴上的每个点，不得超过 k次被覆盖。

思路：首先要理解建图思路，首先有一个基图，相邻点之间都有边，花费为0，容量为 k，然后再根据所给数据 u，v, w 建图，u，v,加一条容量为 1，花费为 - w的边，求最大费用最大流，只需将权值变为负数即可求出最短路，相反数即为最大值。

最小费用最大流，就是用SPFA寻找最短路（增广路容量是否大于流量，花费最短路），然后用最大流方法去计算最大流量（容量限制）

理解一下最后画的图应该就懂了。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

#define N 220

int num[N],inf=0x3f3f3f3f;

struct node

{

    int to,nextt;//下一个点 邻接表

    int cap,flow,cost;//容量 流量 花费

} e[N*N]; //邻接表的next

bool book[N*2];

int a[N*2+5],tot,n,k,s,t,id[100010],l[N],r[N],w[N],dis[N*2],way[N*4],head[N*4];//最短距离 记录路径

/*邻接表存图*/

void add(int u,int v,int cap,int cost)

{

    e[tot].to=v;

    e[tot].cap=cap;

    e[tot].cost=cost;

    e[tot].flow=0;

    e[tot].nextt=head[u];

    head[u]=tot++;

    e[tot].to=u;

    e[tot].cost=-1*cost;

    e[tot].flow=0;

    e[tot].cap=0;

    e[tot].nextt=head[v];//正反建图

    head[v]=tot++;

}

bool spfa()

{

    // 寻找0~t的最短路

    for(int i=0;i<=t;i++)

    {

        dis[i]=inf;

        book[i]=0;

        way[i]=-1;

    }

    book[s]=1;

    dis[s]=0;

    queue<int>q;

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        book[u]=0;

        for(int j=head[u];j!=-1;j=e[j].nextt)

        {

            int v=e[j].to;

            if(e[j].cap>e[j].flow&&dis[v]>dis[u]+e[j].cost)//附加条件：当容量大于流量

            {

                dis[v]=dis[u]+e[j].cost;

                way[v]=j;//记录边？

                if(!book[v])

                {

                    book[v]=1;

                    q.push(v);

                }

            }

        }

    }

    if(dis[t]!=inf)//存在增广路可以到达 t

        return 1;

    return 0;

}

int MCMF()

{

    int flow=0,cost=0;

    while(spfa())

    {

        int minn=inf;

        for(int  i=way[t];i!=-1;i=way[e[i^1].to])

            minn=min(minn,e[i].cap-e[i].flow);//找出最小花费

        for(int i=way[t];i!=-1;i=way[e[i^1].to])

        {

            e[i].flow+=minn;

            e[i^1].flow-=minn;//异或小技巧；1->2  2>1正反边

            cost+=e[i].cost*minn;

        }

        flow+=minn;//计算最大流量？好像没用

    }

    return cost;

}

int main()

{

    int z;

    scanf("%d",&z);

    while(z--)

    {

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

        int p=0;

        memset(head,-1,sizeof(head));

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

        {

            scanf("%d%d%d",&l[i],&r[i],&w[i]);

            a[++p]=l[i];

            a[++p]=r[i];

        }

        sort(a+1,a+p+1);

        tot=1;

        /*重新编号  去重貌似有函数*/

        id[a[1]]=tot++;

        for(int i=2; i<=p; i++)

        {

            if(a[i]!=a[i-1])

                id[a[i]]=tot++;

        }

        t=tot;

        s=0;//起始点

//        printf("%d %d\n",s,t);

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

//            printf("%d %d\n",id[l[i]],id[r[i]]);

        tot=0;

        for(int i=0;i<=t;i++)

            add(i,i+1,k,0);

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

            add(id[l[i]],id[r[i]],1,-w[i]);//为什么是负权

        printf("%d\n",MCMF()*-1);

    }

    return 0;

}

巴特西

POJ 3680 Intervals 最小费用最大流（MCMF算法）

最新文章

热门文章