POJ3680：Intervals（离散化+最大流最小费用）

Intervals

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 9320		Accepted: 4014

题目链接：http://poj.org/problem?id=3680

Description:

You are given N weighted open intervals. The ith interval covers (a_i, b_i) and weighs w_i. Your task is to pick some of the intervals to maximize the total weights under the limit that no point in the real axis is covered more than k times.

Input:

The first line of input is the number of test case.
The first line of each test case contains two integers, N and K (1 ≤ K ≤ N ≤ 200).
The next N line each contain three integers a_i, b_i, w_i(1 ≤ a_i < b_i ≤ 100,000, 1 ≤ w_i ≤ 100,000) describing the intervals.
There is a blank line before each test case.

Output:

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

Sample Input：

4

3 1

1 2 2

2 3 4

3 4 8

3 1

1 3 2

2 3 4

3 4 8

3 1

1 100000 100000

1 2 3

100 200 300

3 2

1 100000 100000

1 150 301

100 200 300

Sample Output:

题意：

给出n个开区间，每个区间都有其权值，现在要求选择权值和最大的几个区间，并且每个点被区间覆盖的次数不超过k。注意这里的点不是整数点，是数轴上面所有的点。

题解:

区间覆盖的权值问题也可以用网络流...orz

我们并不关系区间边界的具体大小，只需要知道其相对大小就行了，所以我们可以考虑进行离散化，以免空间太大数组不能存储。

这里我们首先将点排序、去重、离散化后，0->1,1->2....p->p+1连一条容量为k的边，表示经过这些边的流量不能超过k。

然后根据我们输入的区间，比如离散化后的点为p,q，那么连一条p->q容量为1费用为相应负权值的边。

最后跑个最大流量最小费用就行啦~

这样建图为什么是正确的呢？我想的是总流量不超过k则限制了每个点的覆盖次数，对于两个不相交的区间，那么一个流则可以跑完。对于相交的区间，则需要多的流才能够跑完。

这种建图方式虽然不是很直观，但是yy一下就好了。

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <vector>

#include <queue>

#define mp make_pair

#define fir first

#define sec second

#define INF 1e9

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int N = ;

int n,k,T;

int head[N],vis[N],d[N],a[N],pa[N],pre[N];

struct Edge{

    int v,next,c,w;

}e[N*N<<];

int tot ;

void adde(int u,int v,int c,int w){

    e[tot].v=v;e[tot].next=head[u];e[tot].w=w;e[tot].c=c;head[u]=tot++;

    e[tot].v=u;e[tot].next=head[v];e[tot].w=-w;e[tot].c=;head[v]=tot++;

}

int spfa(int s,int t,int &flow,int &cost){

    for(int i=;i<=t;i++) d[i]=a[i]=INF;d[s]=;

    memset(vis,,sizeof(vis));vis[s]=;

    memset(pre,-,sizeof(pre));memset(pa,-,sizeof(pa));

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

    while(!q.empty()){

        int u=q.front();q.pop();vis[u]=;

        for(int i=head[u];i!=-;i=e[i].next){

            int v=e[i].v;

            if(e[i].c> && d[v]>d[u]+e[i].w){

                d[v]=d[u]+e[i].w;

                pa[v]=u;pre[v]=i;

                a[v]=min(a[u],e[i].c);

                if(!vis[v]){

                    vis[v]=;

                    q.push(v);

                }

            }

        }

    }

    if(d[t]==INF) return ;

    flow+=a[t];

    cost+=a[t]*d[t];

    for(int i=t;i!=-;i=pa[i]){

        int edge = pre[i];

        e[edge].c-=a[t];

        e[edge^].c+=a[t];

    }

    return ;

}

int Min_cost(int s,int t){

    int flow=,cost=;

    while(spfa(s,t,flow,cost));

    return cost;

}

int main(){

    cin>>T;

    while(T--){

        tot=;memset(head,-,sizeof(head));

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

        vector <int> x;

        vector <pair<pii,int> > g;

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

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            x.push_back(u);x.push_back(v);

            g.push_back(mp(mp(u,v),w));

        }

        sort(x.begin(),x.end());

        x.erase(unique(x.begin(),x.end()),x.end());

        int len = x.size();

        for(int i=;i<=len;i++) adde(i,i+,k,);

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

            int u=g[i].fir.fir,v=g[i].fir.sec,w=g[i].sec;

            int p1 = lower_bound(x.begin(),x.end(),u)-x.begin()+;

            int p2 = lower_bound(x.begin(),x.end(),v)-x.begin()+;

            adde(p1,p2,,-w);

        }

        printf("%d\n",-Min_cost(,len+));

    }

    return ;

}

/*

2

4 2

6 10 4

1 8 10

10 19 3

8 14 1

4 2

2 4 4

1 3 3

4 6 2

3 5 1

*/

巴特西

POJ3680：Intervals（离散化+最大流最小费用）

最新文章

热门文章