思路

　　由要求线段的长度，很容易想到应该把问题转化成求费用流。

　　通过限制好相邻点之间的流量，就能保证每个区间内保证不会有使用次数超过x次的点。

　　然后再把区间作为主要要求的目标，把一个区间看作一个有点权的点连在图中。

　　因为区间只能使用一次，且为了计算长度，我们让这个区间的费用为 -len。

　　这样跑MCMF所得出的mincost就是跑满图时得到的最大区间长度。

　　但是由于本题数据给出的区间范围相当大

　　正常的建图只能过掉前六个点

　　考虑到 n 很小，说明区间大时不需要用的点很多

　　所以这些点之间连边与否是完全不影响整张图的流量的

　　这时考虑离散化，就能在找残量网络和更新最大费用时减少毫不相干的时空支出

　　

CODE

 

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 const int maxn = 1e5 +7;
  9 const int inf  = 0x3f3f3f3f;
 10 
 11 int n, m, s, t;
 12 int head[maxn],pre[maxn],inq[maxn],dis[maxn];
 13 int a[maxn];
 14 int cnt = 1;
 15 int path[2][maxn];
 16 int mincost = 0, maxflow = 0;
 17 struct edge {
 18     int u,to,nxt,w,c;
 19 }e[maxn << 1];
 20 int tot[5];
 21 
 22 template<class T>inline void read(T &res)
 23 {
 24     char c;T flag=1;
 25     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 26     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 27 }
 28 
 29 inline void BuildGraph(int u, int v, int w, int cost)
 30 {
 31     e[++cnt] = (edge){u, v, head[u], w,  cost}, head[u] = cnt;
 32     e[++cnt] = (edge){v, u, head[v], 0, -cost}, head[v] = cnt;///反向边
 33 }
 34 
 35 queue<int> q;
 36 
 37 inline void init() {
 38     memset(head, 0, sizeof(head));
 39     memset(pre, 0, sizeof(pre));
 40     memset(inq, 0, sizeof(inq));
 41     memset(dis, 0, sizeof(dis));
 42     memset(e, 0, sizeof(e));
 43     while(!q.empty()) {
 44         q.pop();
 45     }
 46     mincost = maxflow = 0;
 47     cnt = 1;
 48 }
 49 
 50 bool SPFA(int x)
 51 {
 52     memset(inq, 0, sizeof(inq));
 53     for(int i = s; i <= t; i++) {
 54         dis[i] = inf;
 55     }
 56     q.push(x);
 57     dis[x] = 0;
 58     inq[x] = 1;
 59     while(!q.empty()) {
 60         int u = q.front();
 61         q.pop();
 62         inq[u] = 0;
 63         for(int i = head[u]; i; i = e[i].nxt) {
 64             int v = e[i].to, w = e[i].c;
 65             if(e[i].w > 0) {
 66                 if(dis[u] + w < dis[v]) {
 67                     dis[v] = dis[u] + w;
 68                     pre[v] = i;
 69                     if(!inq[v]) {
 70                         q.push(v);
 71                         inq[v] = 1;
 72                     }
 73                 }
 74             }
 75         }
 76     }
 77     if(dis[t] == inf)
 78         return 0;
 79     return 1;
 80 }
 81 
 82 void MCMF()
 83 {
 84     while(SPFA(s)) {
 85         int temp = inf;
 86         for(int i = pre[t]; i; i = pre[e[i].u]) {
 87             temp = min(temp, e[i].w);
 88         }
 89         for(int i = pre[t]; i; i = pre[e[i].u]) {
 90             e[i].w   -= temp;
 91             e[i^1].w += temp;
 92             mincost += e[i].c * temp;
 93             //printf("e[%d].c:%d\n",i, e[i].c);
 94             //printf("ans:%d\n",ans);
 95         }
 96         //maxflow += temp;
 97     }
 98 }
 99 
100 int k;
101 int l[maxn], r[maxn];
102 int ls[maxn], lss[maxn];
103 int totls, totlss;
104 int len[maxn];
105 
106 void Unique() {
107     for ( int i = 1; i <= n; ++i ) {
108         for ( int j = 1; j <= totlss; ++j ) {
109             if(l[i] == lss[j]) {
110                 l[i] = j;
111             }
112             if(r[i] == lss[j]) {
113                 r[i] = j;
114             }
115         }
116     }
117 }
118 
119 int main()
120 {
121     //freopen("data.txt", "r", stdin);
122     read(n); read(k);
123     init();
124     for ( int i = 1; i <= n; ++i ) {
125         read(l[i]); read(r[i]);
126         ls[++totls] = l[i];
127         ls[++totls] = r[i];
128         len[i] = r[i] - l[i];
129     }
130     sort(ls + 1, ls + 1 + totls);
131     for ( int i = 1; i <= totls; ++i ) {
132         if(ls[i] == ls[i-1])
133             continue;
134         lss[++totlss] = ls[i];
135     }
136     Unique();
137     s = 0;
138     for ( int i = 1; i <= n; ++i ) {
139         t = max(t, r[i]);
140         BuildGraph(l[i], r[i], 1, -len[i]);
141     }
142     for ( int i = 0; i <= t; ++i ) {
143         BuildGraph(i, i + 1, k, 0);
144     }
145     ++t;
146     MCMF();
147     cout << -mincost << endl;
148     return 0;
149 }
View Code

 

 

 

#include  <bits/stdc++.h>
#define  dbg( x) cout  << #x  <<  "="  << x  << endl
#define  eps  1 e - 8
#define  pi  acos( - 1.0)

using  namespace std;
typedef  long  long LL;
const  int maxn  =  1 e 5  + 7;
const  int inf   =  0x 3f3f3f3f;

int n, m, s, t;
int  head[maxn], pre[maxn], inq[maxn], dis[maxn];
int  a[maxn];
int cnt  =  1;
int  path[ 2][maxn];
int mincost  =  0, maxflow  =  0;
struct  edge {
     int u,to,nxt,w,c;
} e[maxn  <<  1];
int  tot[ 5];

template< class  T> inline  void  read( T  & res)
{
     char c;T flag = 1;
     while((c = getchar()) < '0' ||c > '9') if(c == '-')flag =- 1;res =c - '0';
     while((c = getchar()) >= '0' &&c <= '9')res =res * 10 +c - '0';res *=flag;
}

inline  void  BuildGraph( int  u,  int  v,  int  w,  int  cost)
{
     e[ ++cnt]  = (edge){u, v,  head[u], w,  cost},  head[u]  = cnt;
     e[ ++cnt]  = (edge){v, u,  head[v],  0,  -cost},  head[v]  = cnt; ///反向边
}

queue < int > q;

inline  void  init() {
     memset(head,  0,  sizeof(head));
     memset(pre,  0,  sizeof(pre));
     memset(inq,  0,  sizeof(inq));
     memset(dis,  0,  sizeof(dis));
     memset(e,  0,  sizeof(e));
     while( ! q. empty()) {
         q. pop();
    }
    mincost  = maxflow  =  0;
    cnt  =  1;
}

bool  SPFA( int  x)
{
     memset(inq,  0,  sizeof(inq));
     for( int i  = s; i  <= t; i ++) {
         dis[i]  = inf;
    }
     q. push(x);
     dis[x]  =  0;
     inq[x]  =  1;
     while( ! q. empty()) {
         int u  =  q. front();
         q. pop();
         inq[u]  =  0;
         for( int i  =  head[u]; i; i  =  e[i]. nxt) {
             int v  =  e[i]. to, w  =  e[i]. c;
             if( e[i]. w  >  0) {
                 if( dis[u]  + w  <  dis[v]) {
                     dis[v]  =  dis[u]  + w;
                     pre[v]  = i;
                     if( ! inq[v]) {
                         q. push(v);
                         inq[v]  =  1;
                    }
                }
            }
        }
    }
     if( dis[t]  == inf)
         return  0;
     return  1;
}

void  MCMF()
{
     while( SPFA(s)) {
         int temp  = inf;
         for( int i  =  pre[t]; i; i  =  pre[ e[i]. u]) {
            temp  =  min(temp,  e[i]. w);
        }
         for( int i  =  pre[t]; i; i  =  pre[ e[i]. u]) {
             e[i]. w    -= temp;
             e[i ^ 1]. w  += temp;
            mincost  +=  e[i]. c  * temp;
            //printf("e[%d].c:%d\n",i, e[i].c);
            //printf("ans:%d\n",ans);
        }
        //maxflow += temp;
    }
}

int k;
int  l[maxn],  r[maxn];
int  ls[maxn],  lss[maxn];
int totls, totlss;
int  len[maxn];

void  Unique() {
     for (  int i  =  1; i  <= n;  ++i ) {
         for (  int j  =  1; j  <= totlss;  ++j ) {
             if( l[i]  ==  lss[j]) {
                 l[i]  = j;
            }
             if( r[i]  ==  lss[j]) {
                 r[i]  = j;
            }
        }
    }
}

int  main()
{
    //freopen("data.txt", "r", stdin);
     read(n);  read(k);
     init();
     for (  int i  =  1; i  <= n;  ++i ) {
         read( l[i]);  read( r[i]);
         ls[ ++totls]  =  l[i];
         ls[ ++totls]  =  r[i];
         len[i]  =  r[i]  -  l[i];
    }
     sort(ls  +  1, ls  +  1  + totls);
     for (  int i  =  1; i  <= totls;  ++i ) {
         if( ls[i]  ==  ls[i - 1])
             continue;
         lss[ ++totlss]  =  ls[i];
    }
     Unique();
    s  =  0;
     for (  int i  =  1; i  <= n;  ++i ) {
        t  =  max(t,  r[i]);
         BuildGraph( l[i],  r[i],  1,  - len[i]);
    }
     for (  int i  =  0; i  <= t;  ++i ) {
         BuildGraph(i, i  +  1, k,  0);
    }
     ++t;
     MCMF();
    cout  <<  -mincost  << endl;
     return  0;
}