POJ 3680 Intervals(费用流+离散化） - c++编程基础

TOP

POJ 3680 Intervals(费用流+离散化）

2015-07-20 17:50:27 来源: 作者: 【大中小】浏览:2次

题目地址：POJ 3680

这题的建图真心想不出来。建图思维还是不够开阔，不够大胆。

这题要先对坐标进行离散化。可以用左边的点发出一条到右边的点的边，容量为1，费用为负的权值。然后从左往右将依次将相邻的两个点都连起来，权值为0，容量为k，也就是说，如果选了这个区间，就会从费用为负数的边流过去，否则，就是从这个费用为0的边流过去。然后建立一个超级源点与最左边的点相连，权值为0，容量为k，这样就保证了重叠数之多为k，因为增广路上所经过的区间必定是不重合的，而流量只有k，所以满足题意。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; const int INF=0x3f3f3f3f; int head[1000], source, sink, cnt, fei[10000], q[10000], flow, cost; int d[1000], vis[1000], cur[1000], f[1000]; struct node { int u, v, cap, cost, next; }edge[1000000]; void add(int u, int v, int cap, int cost) { edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].cost=cost; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].cost=-cost; edge[cnt].next=head[v]; head[v]=cnt++; } int spfa() { memset(d,INF,sizeof(d)); memset(vis,0,sizeof(vis)); queue
             
              q; q.push(source); d[source]=0; f[source]=INF; cur[source]=-1; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(d[v]>d[u]+edge[i].cost&&edge[i].cap) { d[v]=d[u]+edge[i].cost; f[v]=min(f[u],edge[i].cap); cur[v]=i; if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(d[sink]==INF) return 0; flow+=f[sink]; cost-=f[sink]*d[sink]; for(int i=cur[sink];i!=-1;i=cur[edge[i^1].v]) { edge[i].cap-=f[sink]; edge[i^1].cap+=f[sink]; } return 1; } void mcmf() { flow=cost=0; while(spfa()) ; printf("%d\n",cost); } int get(int x, int high) { int low=1, mid; while(low<=high) { mid=low+high>>1; if(fei[mid]==x) return mid; else if(fei[mid]>x) high=mid-1; else low=mid+1; } } int main() { int t, n, k, i, tot, a[300], b[300], max1, j, c[300]; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); memset(head,-1,sizeof(head)); cnt=0; source=0; tot=1; max1=-1; for(i=1;i<=n;i++) { scanf("%d%d%d",&a[i],&b[i],&c[i]); q[2*i-1]=a[i]; q[2*i]=b[i]; } sort(q+1,q+2*n+1); fei[1]=q[1]; for(i=2;i<=2*n;i++) { if(q[i]!=q[i-1]) fei[++tot]=q[i]; } sink=tot+1; add(source,1,k,0); for(i=1;i<=n;i++) { int l=get(a[i],tot); int r=get(b[i],tot); add(l,r,1,-c[i]); //printf("%d %d\n",l,r); } for(i=2;i<=tot;i++) { add(i-1,i,k,0); } add(tot,sink,k,0); mcmf(); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 3169 Layout (差分约束系统）	下一篇：uva 501 - Black Box(优先队列)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: