The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 3686 The Windy's

好题啊,才发现用网络流也能解这么有实际意义的问题,说不定以后再工程中真的能遇到呢。
网络上的方法是用KM,不过个人比较喜欢用最小费用,就是跑得慢了点。
一点教训吧:这个题里面总点数应该是2500+50+2
最小的边数应该是 (2500*50+50+2500)*2,刚开始没有乘以2,结果猛RE.后来想到网络流里是要建正反边的,汗啊。
建图的代码如下:
int main()
{

    
int t ;
    
int i,j,k;
    scanf(
"%d",&t);
    
while(t--)
    
{
        len
=0;

        
int tem;
        scanf(
"%d%d",&m,&n);
        
for(i=0;i<n*m+m+2;i++)
            adj[i]
=NULL;
        
for (i = 0; i < m; i++)             
        
for (j = 0; j < n; j++)
        
{
            scanf(
"%d"&tem);     
            
for (k = 0; k < m; k++)              
                insert(i,m
+j*m+k,1,(k + 1* tem); 
        }

        
int s=n*m+m;
        
int t=n*m+m+1;
        
for(i=0;i<m;i++)
            insert(s,i,
1,0);
        
for(i=m;i<n*m+m;i++)
            insert(i,t,
1,0);
        printf(
"%.6lf\n",(double)mincostflow(t+1,s,t)/(double)m);

        

    }

    
return 0;

}

posted on 2010-03-28 23:46 abilitytao 阅读(248) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理