CF-164C. Machine Programming(最小费用最大流)

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

题意：

给你n个任务，k个机器，n个任务的起始时间，持续时间，完成任务的获利

每个机器可以完成任何一项任务，但是同一时刻只能完成一项任务，一旦某台机器在完成某项任务时，直到任务结束，这台机器都不能去做其他任务

最后问你当获利最大时，应该安排那些机器工作，即输出方案

分析：

要求的是最大费用，因此将费用取负就可以用最小费用最大流算法了

建图很重要。如果图建的复杂的话，可能就会超时了的！

新建源汇S T‘

对任务按照起始时间s按升序排序

拆点：

u 向 u'连一条边容量为 1 费用为 -c,

u' 向 T连一条边容量为 inf 费用为 0；

如果任务u完成后接下来最先开始的是任务v

则从u' 向 v连一条边，容量inf 费用 0.

另外，任务从前往后具有传递性，所以必须是第i个任务向第i+1个任务建边，容量为inf

// File Name: 164-C.cpp
// Author: Zlbing
// Created Time: 2013年08月13日 星期二 14时57分55秒

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
const int MAXN=2e3+100;
struct Edge{
    int from,to,cap,flow,cost;
};
struct MCMF{
    int n,m,s,t;
    vector<Edge>edges;
    vector<int> G[MAXN];
    int inq[MAXN];
    int d[MAXN];
    int p[MAXN];
    int a[MAXN];
    void init(int n){
        this->n=n;
        for(int i=0;i<=n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int cap,int cost){
        edges.push_back((Edge){from,to,cap,0,cost});
        edges.push_back((Edge){to,from,0,0,-cost});
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool BellmanFord(int s,int t,int& flow,int& cost){
        for(int i=0;i<=n;i++)d[i]=INF;
            CL(inq,0);
        d[s]=0;inq[s]=1;p[s]=0;a[s]=INF;

        queue<int>Q;
        Q.push(s);
        while(!Q.empty()){
            int u=Q.front();Q.pop();
            inq[u]=0;
            for(int i=0;i<(int)G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
                    d[e.to]=d[u]+e.cost;
                    p[e.to]=G[u][i];
                    a[e.to]=min(a[u],e.cap-e.flow);
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=1;
                    }
                }
            }
        }
        if(d[t]==INF)return false;
        flow+=a[t];
        cost+=d[t]*a[t];
        int u=t;
        while(u!=s){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
            u=edges[p[u]].from;
        }
        return true;
    }
    int Mincost(int s,int t){
        int flow=0,cost=0;
        while(BellmanFord(s,t,flow,cost));
        return cost;
    }
};
struct node{
    int u, v,cost,id ;
    bool operator <(const node &rsh)const
    {
        return u<rsh.u;
    }
}pos[MAXN];
MCMF solver;
int ans[MAXN];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int a,b,c;
        solver.init(2*n+5);
        REP(i,0,n-1)
        {
            scanf("%d%d%d",&a,&b,&c);
            pos[i]=(node){
                a,a+b-1,c,i
            };
        }
        sort(pos,pos+n);
        int s=n*2,t=n*2+1;
        REP(i,0,n-1)
        {
            solver.AddEdge(i,i+n,1,-pos[i].cost);
            solver.AddEdge(i+n,t,INF,0);
            if(i<n-1)solver.AddEdge(i,i+1,INF,0);
            for(int j=i+1;j<n;j++)
            {
                if(pos[i].v<pos[j].u)
                {
                    solver.AddEdge(i+n,j,INF,0);
                    break;
                }
            }
        }
        solver.AddEdge(s,0,m,0);
        solver.AddEdge(n-1,t,m,0);
        solver.Mincost(s,t);
       //printf("cost=%d\n",-tmp);
        CL(ans,0);
        for(int i=0;i<(int)solver.edges.size();i++)
        {
            Edge e=solver.edges[i];
            if(e.cap)
            {
                int u=e.from;
                if(u!=s&&u!=t&&u<n&&e.flow==e.cap)
                {
                    ans[pos[u].id]=1;
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            if(i)printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}