The Fourth Dimension Space

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

[POI2006]Szk-Schools 最小费用最大流

题意就是N个学校,每个学校有一个编号,编号可以重复。现在要求每个学校有一个独立的编号,但是每个学校可以接受的编号有一个范围,在这个范围内,编号每变动1将付出的话费是D。求是否有可行方案并给出最小花费。
显然X部分是所有的学校,Y部分是新的编号,按顺序我们把学校设置成1—N,设置超级源点s,s向每个X侧的节点连一条费用是0,流量是1的边,把他们对应的编号设置成节点N+1- 2*N,X部和Y部的边用计算出来的花费连边,流量是1,Y部每个节点向t连一条费用是0流量是1的边,求最小费用最大流即可。

模板就不贴了,构图部分代码如下:
void creat(int n,int s,int t)
{
    flowsum
=0;
    
int a,b,c,d;
    
int i;

    
for(i=1;i<=n;i++)
    
{
        insert(s,i,
1,0);
        insert(i
+n,t,1,0);

        scanf(
"%d%d%d%d",&a,&b,&c,&d);
        
int j;
        
for(j=b;j<=c;j++)
        
{
            insert(i,j
+n,1,abs(j-a)*d);
        }

    }


    
}


void init(int n)
{
    
int i;
    
for(i=0;i<n;i++)
        adj[i]
=NULL;
    len
=0;
}


int main()
{

    
int n;
    
int s,t;

    scanf(
"%d",&n);
    init(
2*n+2);
    s
=0;
    t
=2*n+1;
    creat(n,s,t);
    
int ans=mincostflow(t+1,s,t);
    
if(flowsum!=n)
        printf(
"NIE\n");
    
else
        printf(
"%d\n",ans);
    
return 0;
}

posted on 2010-07-17 15:30 abilitytao 阅读(363) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理