注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 3680  

2010-01-10 12:09:05|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
经典的图论建模题目,首先将点进行离散化,排序,然后加入源s和汇t,s向第一个点连边,容量为k,费用0,第一个点向第二个点连边,容量为k,费用0。。。。。。。。。最后一个点向t连边,容量为k,费用0
然后对于原来的边(a,b)排序后对应的为(c,d),则c向d连边,容量1,费用-c,然后进行最小费用最大流即可
由于此题可能存在重边所以不能使用邻接矩阵,然后我使用了zkw的费用流,对于负权边,运行两次,第一次求最小费用可行流,第二次求最小费用最大流,并使用了slack和多叉搜索的优化,速度果然很快
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxint=~0U>>1;
int n,m,k,ti,pi[500],v[500],cost[2200],pnt[2200],nxt[2200],head[500],flow[2200];
int b[205],c[500],sum,ss,e,mincost,temp,slack[500];
struct qq{
       int a,b;
}a[500];
int compar(qq x,qq y){
    return x.a<y.a;
}
int aug(int no,int mm) 
   if(no==sum-1)return mincost+=(pi[ss]-pi[sum-1])*mm,mm; 
   v[no]=true; 
   int old=mm,d=0;
   for(int i=head[no];i!=-1;i=nxt[i]) 
      if(flow[i]&&!v[pnt[i]])
        if(!(temp=pi[pnt[i]]+cost[i]-pi[no])){ 
          d=aug(pnt[i],old<flow[i]?old:flow[i]);
          flow[i]-=d,flow[i^1]+=d;
          old-=d; 
          if(!old)
            break;
        }
        else if (temp<slack[pnt[i]])
                 slack[pnt[i]]=temp;
   return mm-old; 
bool modlabel() 
   int d=maxint,c; 
   for(int i=0;i<sum;i++){
     if(!v[i]&&slack[i]<d)d=slack[i]; 
     slack[i]=maxint;
   }
   if(d==maxint)return false; 
   for(int i=0;i<sum;i++)if(v[i]) pi[i]+=d;
   return true; 
inline void addedge(int s0,int t0,int u0,int c0){
      cost[e]=c0;pnt[e]=t0;nxt[e]=head[s0];flow[e]=u0;head[s0]=e++;
      cost[e]=-c0;pnt[e]=s0;nxt[e]=head[t0];flow[e]=0;head[t0]=e++; 
}
int main(){
    scanf("%d",&ti);
    while(ti--){
      memset(pi,0,sizeof(pi));
      memset(head,-1,sizeof(head));
      memset(nxt,-1,sizeof(nxt));
      mincost=e=0;
      scanf("%d%d",&n,&k);
      for(int i=0;i<2*n+4;i++)
           slack[i]=maxint;
      for(int i=0;i<n;i++){
        scanf("%d%d%d",&a[i].a,&a[i+n].a,&b[i]);
        a[i].b=i;
        a[i+n].b=i+n;
      }
      sort(a,a+2*n,compar);
      c[a[0].b]=sum=1;
      for(int i=1;i<2*n;i++){
        if(a[i-1].a!=a[i].a)
          sum++;
        c[a[i].b]=sum;
      }
      for(int i=0;i<=sum;i++)
        addedge(i,i+1,k,0);
      for(int i=0;i<2*n;i++)
       if(a[i].b<n){
        addedge(c[a[i].b+n],c[a[i].b],1,b[a[i].b]);
        addedge(sum+2,c[a[i].b+n],1,0);
        addedge(c[a[i].b],sum+3,1,0);
        mincost-=b[a[i].b];
      }
      addedge(sum+1,0,maxint,0);
      sum+=4;ss=sum-2;
      do do memset(v,0,sizeof(v));
      while(aug(sum-2,maxint));
      while(modlabel());
      sum-=2;ss=0;
      flow[e-1]=0;
      do do memset(v,0,sizeof(v));
      while(aug(0,maxint));
      while(modlabel());
      printf("%d\n",-mincost);
    }
    return 0;
}

  评论这张
 
阅读(1218)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018