The Fourth Dimension Space

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

POJ 2391 Ombrophobic Bovines 网络流

这提相当经典啊,这题相当猥琐啊。。。。
无向图中给出N个点,M条边,每个点有当前囤积流量和最大容量,任意两个点之间有距离,首先保证所有的流量都可以被节点吸收(即不超过最大容量),然后将流量跑的最大距离限制到最小。
做法:SAP+二分+Floyd
1.首先预处理出任意两点之间的最短路,二分最大距离mid;
2.将每个节点拆成i*2 i*2+1,i*2+1代表流出的点out[i],i*2代表流进的点in[i],前者向后者连一条INF的边。
3.建立超级源s,向每个点in[i],连一条当前囤积流量的边,每个点out[i]向超级汇t连一条最大容量的边。
4.在floyd之后的数组中枚举每两个点之间的最短距离,如果<=mid就建立一条out[i]->in[j]的边
跑最大流,如果满流,下降上界,否则提高下界。

这题做了收获很大,学会了控制初始流量的方法和最后流量全部控制在容量内的方法。
另外就是拆点,分成两个点之后,限制了只要进来的流量就一定囤积在该点,由于这个点本身有初始流量,两个点之间连的那条边可以保证自己的流量也可以不流走。非常精彩的构图^_^
PS:顺便说一下的是:虽然这个图是无向图,但是根据题意,走任意方向互不干扰,所以可以拆成两条有向边。一旦有流量经过这条边,那么流量不会流走,也就说明这个流量必须也只能走这么长的距离,这个锁定技巧很不错,于是就能二分了。。。


int n,m;
int s,t;
int now[maxn];
int cap[maxn];

bint mat[maxn][maxn];


bint tol
=0;
void input()
{
    tol
=0;
    
for(int i=0;i<n;i++)
        
for(int j=0;j<n;j++)
        {
            
if(i==j)mat[i][j]=0;
            
else mat[i][j]=INF;
        }

    
for(int i=0;i<n;i++)
    {
        scanf(
"%d%d",&now[i],&cap[i]);
        tol
+=now[i];
    }
    
for(int i=0;i<m;i++)
    {
        
int u,v;
        bint w;
        scanf(
"%d%d%lld",&u,&v,&w);
        u
--;
        v
--;
        
if(w<mat[u][v])
            mat[u][v]
=mat[v][u]=w;
    }

}


void floyd()
{
    
for(int k=0;k<n;k++)
        
for(int i=0;i<n;i++)
            
for(int j=0;j<n;j++)
            {
                
if(mat[i][k]!=INF&&mat[k][j]!=INF)
                    
if(mat[i][k]+mat[k][j]<mat[i][j])
                        mat[i][j]
=mat[i][k]+mat[k][j];
            }
}


//in node : i*2;
//out node: i*2+1
//node sum: [0,2*n-1]
//s: 2*n
//t: 2*n+1
//tol:2*n+2

bool check(bint mid)
{
    
for(int i=0;i<2*n+2;i++)
        adj[i]
=NULL;
    len
=0;
    
for(int i=0;i<n;i++)
        
for(int j=0;j<n;j++)
        {
            
if(i==j)continue;
            
if(mat[i][j]!=INF&&mat[i][j]<=mid)
            {
                insert(i
*2+1,j*2,INF);
            }
        }
    
for(int i=0;i<n;i++)
    {
        insert(s,i
*2+1,now[i]);
        insert(i
*2+1,i*2,INF);
    }
    
for(int i=0;i<n;i++)
        insert(i
*2,t,cap[i]);
    
if(sap(t+1,s,t)==tol)
        
return true;
    
else
        
return false;
}

int main()
{

    
while(scanf("%d%d",&n,&m)!=EOF)
    {
        input();
        floyd();
        s
=2*n;
        t
=2*n+1;
        bint l
=0;
        bint r
=INF;
        bint ans
=-1;
        
while(l<=r)
        {
            bint mid
=(l+r)>>1;
            
if(check(mid)==true)
            {
                r
=mid-1;
                ans
=mid;
            }
            
else
                l
=mid+1;
        }
        printf(
"%lld\n",ans);
    }
    
return 0;
}


posted on 2010-11-11 20:01 abilitytao 阅读(1963) 评论(1)  编辑 收藏 引用

评论

# re: POJ 2391 Ombrophobic Bovines 网络流 2010-11-17 00:36 xie

学习了!!!!!!!!!  回复  更多评论   


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