Modular Production Line

Modular Production Line

时空限制: 1000ms /65536K

An automobile factory has a car production line. Now the market is oversupply and the production line is often shut down. To make full use of resources, the manager divides the entire production line into

Input

The first line of input is

The first line of each test case contains three integers,

The next

$1≤N≤10^5$

$1≤Wi≤10^5$

Output

For each test case output the maximum value in a separate line.

样例输入

4
10 1 3
1 2 2
2 3 4
3 4 8
10 1 3
1 3 2
2 3 4
3 4 8
100000 1 3
1 100000 100000
1 2 3
100 200 300
100000 2 3
1 100000 100000
1 150 301
100 200 300

样例输出

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

最大权不相交路径问题.与最长K可重区间问题几乎是一样的。

有一点不同的是在最长K可重区间问题中每个区间端点是不算在区间交集里的，而在这个问题中区间端点是算在区间交集里的。把每个区间右端点加一，就可以转化为最长K可重区间问题了。

还有一点要注意的是，在最长K可重区间问题中，参考博客给了两种解法，而这里的数据量比较大，因此只能用第二种的离散化方法来写。

#include<bits/stdc++.h>
#define INF INT_MAX/2
#define N 800
using namespace std;

typedef struct
{
    int u,v,next;
    int flow,cost;
}ss;

ss edg[2*N];
int head[N];
int now_edge=0;

void addedge(int u,int v,int flow,int cost)
{
    edg[now_edge]=(ss){u,v,head[u],flow,cost};
    head[u]=now_edge++;
    edg[now_edge]=(ss){v,u,head[v],0,-cost};
    head[v]=now_edge++;
}

bool spfa(int s,int t,int &flow,int &cost)
{
    int dis[N];
    for(int i=0;i<N;i++)dis[i]=INF;
    dis[s]=0;

    int vis[N]={0};
    vis[s]=1;

    queue<int>q;
    q.push(s);

    int addflow[N]={0};
    addflow[s]=INF;

    int pre[N]={0};

    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=0;

        for(int i=head[now];i!=-1;i=edg[i].next)
        {
            ss e=edg[i];

            if(e.flow>0&&dis[e.v]>dis[now]+e.cost)
            {
                dis[e.v]=dis[now]+e.cost;
                addflow[e.v]=min(addflow[now],e.flow);
                pre[e.v]=i;

                if(!vis[e.v])
                {
                    q.push(e.v);
                    vis[e.v]=1;
                }
            }
        }
    }

    if(dis[t]==INF)return false;

    flow+=addflow[t];
    cost+=addflow[t]*dis[t];

    int now=t;
    while(now!=s)
    {
        edg[pre[now]].flow-=addflow[t];
        edg[pre[now]^1].flow+=addflow[t];
        now=edg[pre[now]].u;
    }

    return true;
}

void MCMF(int s,int t,int &flow,int &cost)
{
    while(spfa(s,t,flow,cost));
}



struct
{
    int l,r,value;
}arr[N];

int lsh[N],len_lsh;
int f(int x)
{
    return lower_bound(lsh,lsh+len_lsh,x)-lsh+1;
}

void init()
{
    for(int i=0;i<N;i++)head[i]=-1;
    now_edge=0;
    len_lsh=0;
}

int main()
{
    int t=1;
    scanf("%d",&t);
    while(t--)
    {
        init();
        int n,k,m;
        scanf("%d %d %d",&n,&k,&m);

        for(int i=0;i<m;i++)
        {
            scanf("%d %d %d",&arr[i].l,&arr[i].r,&arr[i].value);
            arr[i].r++;
            lsh[len_lsh++]=arr[i].l;
            lsh[len_lsh++]=arr[i].r;
        }

        sort(lsh,lsh+len_lsh);
        len_lsh=unique(lsh,lsh+len_lsh)-lsh;

        int s=len_lsh+1,t=s+1;
        addedge(s,1,k,0);
        addedge(len_lsh,t,INF,0);
        for(int i=1;i<len_lsh;i++)addedge(i,i+1,INF,0);

        for(int i=0;i<m;i++)addedge(f(arr[i].l),f(arr[i].r),1,-arr[i].value);

        int cost=0,flow=0;
        MCMF(s,t,flow,cost);
        printf("%d
",-cost);
    }
    return 0;
}

View Code