285484026

「网络流 24 题」最长 k 可重区间集
「网络流 24 题」最长 k 可重区间集题解:题意是说选择出一个线段集合,使得任何一个点x含有的区间不超过K条,要...
扫描右侧二维码阅读全文
25
2018/10

「网络流 24 题」最长 k 可重区间集

「网络流 24 题」最长 k 可重区间集
题解:题意是说选择出一个线段集合,使得任何一个点x含有的区间不超过K条,要求求出一个区间集合使得集合中所有区间长度相加的总长度最大

#include <bits/stdc++.h>

const int MAXN = 1000000,INF = 10000000;

using namespace std;

int n,k,s,t,e = 2,top;
int head[MAXN],pri[MAXN],dis[MAXN],H[MAXN];
bool inq[MAXN];

struct node{
    int u,v,w,c,f,next;
}edge[MAXN];

struct node1{
    int u,v;
}Edge[MAXN];

inline void addedge(int u,int v,int w,int c){
    edge[e] = (node){u,v, w,c,0,head[u]};head[u] = e++;
    edge[e] = (node){v,u,-w,0,0,head[v]};head[v] = e++;    
}

inline void init()
{
    scanf("%d %d",&n,&k);

    for(int i = 1;i <= n;i++){
        scanf("%d %d",&Edge[i].u,&Edge[i].v);
        if(Edge[i].u > Edge[i].v) swap(Edge[i].u,Edge[i].v);
        H[++top] = Edge[i].u;
        H[++top] = Edge[i].v;
    }
    sort(H+1,H+top+1);
    top = unique(H+1,H+top+1) - H;
    
    s = 0;t = top;
    addedge(s,1,0,k);addedge(top-1,t,0,k);
    
    for(int i = 1;i < top - 1;i++) addedge(i,i+1,0,INF);
    int pos1,pos2;
    for(int i = 1; i <= n;i++){
        pos1 = lower_bound(H+1,H+top,Edge[i].u) - H;
        pos2 = lower_bound(H+1,H+top,Edge[i].v) - H;
        addedge(pos1,pos2,Edge[i].u-Edge[i].v,1);
    } 
}

queue<int>Q;
inline bool spfa()
{
    for(int i = s;i <= t;i++){
        inq[i] = false;
        dis[i] = INF;
        pri[i] = 0;
    }
    Q.push(s);dis[s] = 0;inq[s] = true;
    while(!Q.empty()){
        int x = Q.front();Q.pop();inq[x] = false;
        for(int i = head[x];i;i = edge[i].next){
            node E = edge[i];
            if(dis[E.v] > dis[x] + E.w && E.c > E.f){
                dis[E.v] = dis[x] + E.w;
                pri[E.v] = i;
                if(!inq[E.v]){
                    Q.push(E.v);
                    inq[E.v] = true; 
                }
            }
            
        }
    }
    return pri[t] ? true : false;
}

inline int MCMF()
{
    int cost = 0,flow = 0,tmp;
    while(spfa())
    {
        tmp = INF;
        for(int i = pri[t];i;i = pri[edge[i^1].v])
            tmp = min(tmp,edge[i].c - edge[i].f);
        for(int i = pri[t];i;i = pri[edge[i^1].v]){
            edge[i].f += tmp;
            edge[i^1].f -= tmp;
            cost += edge[i].w * tmp;
        }
        flow += tmp;
    }
    return cost;
}

int main()
{
    #ifdef hi_archer
      freopen("input.txt", "r", stdin);
    #endif
    init();
    printf("%d",-MCMF());
    return 0;
}
Last modification:October 25th, 2018 at 03:19 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment