当前位置:编程学习 > C/C++ >>

poj 3801 hdu 3157 Crazy Circuits--有源汇 有上下界 最小流

[cpp]
*
hdu 3157
poj 3801
题意:一个电路板,上面有N个接线柱(标号1~N)   还有两个电源接线柱  +  -
然后是 给出M个部件正负极的接线柱和最小电流
求一个可以让所有部件正常工作的总电流  没有则输出impossible
 
其实就是一个 有源汇 有上下界 最小流 问题
 
处理有源汇有上下界最大流问题是:
1.构造附加网络
2.对ss、tt求最大流(ss、tt满流则有解)
3.若有解,对s、t求最大流
 
而有源汇有上下界最小流问题则是:
1.构造附加网络(不添加[t,s]边)
2.对ss、tt求最大流
3.添加[t,s]边
4.对ss、tt求最大流
5.若ss、tt满流,则[t,s]的流量就是最小流
 
这个代码大部分都是从别的题上摘过来的,注释有点乱
*/ 
#include<stdio.h>  
#include<string.h>  
#define inf 0x7fffffff  
struct edge//边    
{   
    int u,v,f,next,b,c;//边的 前节点 后节点 可用流 下条边的编号  原来边上流的上下界    
}e[1500];   
int head[70],in[70],s,t,ss,tt,yong,sum; 
int n,m; 
void ini() 

    memset(head,-1,sizeof(head)); 
    yong=0; 
    memset(in,0,sizeof(in)); 
    s=0,t=n+1,ss=t+1,tt=ss+1;//各节点编号的安排  
    sum=0; 

void adde(int from,int to,int xia,int shang)//加边    
{   //加边    
    e[yong].u=from,e[yong].v=to,e[yong].f=shang-xia,e[yong].b=xia,e[yong].c=shang;   
    e[yong].next=head[from],head[from]=yong++;   
    //同时加它的退边    
    e[yong].u=to,e[yong].v=from,e[yong].f=0,e[yong].b=xia,e[yong].c=shang;   
    e[yong].next=head[to],head[to]=yong++;   
}  
void build() 

    int i;   
    for(i=0;i<=t;++i)   
    {   
        if(in[i]>0)   
            adde(ss,i,0,in[i]);   
        else   
        {   
            adde(i,tt,0,-in[i]);   
            sum+=(-in[i]);   
        }   
    }  

int d[1000],num[1000]; 
int min(int a,int b){return a<b?a:b;}   
int sap_gap(int u,int f,int s,int t)//递归sap    
{   
    if(u==t)   
        return f;   
    int i,v,mind=t,last=f,cost;   
    for(i=head[u];i!=-1;i=e[i].next)   
    {   
        v=e[i].v;   
        int flow=e[i].f;   
        if(flow>0)//参考模版写的时候把flow写成了f    
        {   
            if(d[u]==d[v]+1)   
            {   
                cost=sap_gap(v,min(last,flow),s,t);   
                e[i].f-=cost;   
                e[i^1].f+=cost;   
                last-=cost;   
   
                if(d[s]>=t+1)   
                    return f-last;   
   
                if(last==0)   
                    break;   
            }   
            if(d[v]<mind)   
                mind=d[v];   
        }   
    }   
   
    if(last==f)   
    {   
        --num[d[u]];   
        if(num[d[u]]==0)   
            d[s]=t+1;   
        d[u]=mind+1;   
        ++num[d[u]];   
    }   
    return f-last;   
}   
int max_f(int s,int t) 

    int f=0;   
    memset(d,0,sizeof(d));   
    memset(num,0,sizeof(num));   
    for(num[s]=t+1;d[s]<t+1;)   
        f+=sap_gap(s,inf,s,t);   
    return f;  

int main() 

    int i,dat,u,v,f1,f2,p; 
    char from[10],to[10]; 
    while(scanf("%d%d",&n,&m),n+m) 
    { 
        ini(); 
        for(i=1;i<=m;++i) 
        { 
            scanf("%s%s%d",from,to,&dat); 
            if(from[0]=='+') u=s; 
            else sscanf(from,"%d",&u); 
            if(to[0]=='-') v=t; 
            else sscanf(to,"%d",&v); 
            adde(u,v,dat,inf); 
        &n

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,