743. [网络流24题] 最长k可重区间集

★★★   输入文件：interv.in   输出文件：interv.out   简单对比

时间限制：1 s   内存限制：128 MB

9 13

interv.out

---

这样的区间建图比较好想，因为以前做过用最短路的最小区间覆盖问题，想法类似

BYVOID：

离散化所有区间的端点，把每个端点看做一个顶点，建立附加源S汇T。

1、从S到顶点1（最左边顶点）连接一条容量为K，费用为0的有向边。

2、从顶点2N（最右边顶点）到T连接一条容量为K，费用为0的有向边。

3、从顶点i到顶点i+1(i+1<=2N)，连接一条容量为无穷大，费用为0的有向边。

4、对于每个区间[a,b]，从a对应的顶点i到b对应的顶点j连接一条容量为1，费用为区间长度的有向边。

 

两点：

1.相邻的连一条边，避免了每个点都和s t连边

2.容量限制为k，经过每个点的边数一定<=k

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;const int N=1005,M=1e5+5,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,k,mp[N],m,l[N],r[N],s,t;int Bin(int v){    int l=1,r=m;    while(l<=r){        int mid=(l+r)>>1;        if(mp[mid]==v) return mid;        if(v
          
           e[i].f&&d[v]>d[u]+w){ d[v]=d[u]+w; pos[v]=i;pre[v]=u; if(!inq[v]){ inq[v]=1; if(d[v]