POJ-2135(最小费用最大流模板)-白红宇的个人博客

POJ-2135(最小费用最大流模板)

发布日期：2021-08-14 08:51:21 浏览次数：1 分类：技术文章

本文共 2728 字，大约阅读时间需要 9 分钟。

最小费用最大流模板:

该题注意的几个地方:

1.有重边;

2 3

1 2 1

1 2 2

1 2 3

2.无向图,正反方向均要加边。

因为此题是无向图，所以建边的时候如果建两条费用都是正的边的话，退流时无法修正费用。所以应该建4条边：

第一对：

a->b cost 1

b->a -cost 0

第二对：

b->a cost 1

a->b -cost 0

3.数组要开4*(m+2)

View Code

/*Source CodeProblem: 2135  User: HEU_daoguangMemory: 1532K  Time: 32MSLanguage: G++  Result: AcceptedSource Code*/#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define V 10100#define E 1000100#define inf 99999999using namespace std;int vis[V];int dist[V];int pre[V];struct Edge{    int u,v,c,cost,next;}edge[E];int head[V],cnt;void init(){    cnt=0;    memset(head,-1,sizeof(head));}void addedge(int u,int v,int c,int cost){    edge[cnt].u=u;edge[cnt].v=v;edge[cnt].cost=cost;    edge[cnt].c=c;edge[cnt].next=head[u];head[u]=cnt++;    edge[cnt].u=v;edge[cnt].v=u;edge[cnt].cost=-cost;    edge[cnt].c=0;edge[cnt].next=head[v];head[v]=cnt++;}bool spfa(int begin,int end){    int u,v;    queue
           
             q; for(int i=0;i<=end+2;i++){ pre[i]=-1; vis[i]=0; dist[i]=inf; } vis[begin]=1; dist[begin]=0; q.push(begin); while(!q.empty()){ u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next){ if(edge[i].c>0){ v=edge[i].v; if(dist[v]>dist[u]+edge[i].cost){ dist[v]=dist[u]+edge[i].cost; pre[v]=i; if(!vis[v]){ vis[v]=true; q.push(v); } } } } } return dist[end]!=inf;}int MCMF(int begin,int end){ int ans=0,flow; int flow_sum=0; while(spfa(begin,end)){ flow=inf; for(int i=pre[end];i!=-1;i=pre[edge[i].u]) if(edge[i].c
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define V 10100#define E 1000100#define inf 99999999using namespace std;int vis[V];int dist[V];int pre[V];struct Edge{ int u,v,c,cost,next;}edge[E];int head[V],cnt;void init(){ cnt=0; memset(head,-1,sizeof(head));}void addedge(int u,int v,int c,int cost){ edge[cnt].u=u;edge[cnt].v=v;edge[cnt].cost=cost; edge[cnt].c=c;edge[cnt].next=head[u];head[u]=cnt++; edge[cnt].u=v;edge[cnt].v=u;edge[cnt].cost=-cost; edge[cnt].c=0;edge[cnt].next=head[v];head[v]=cnt++;}bool spfa(int begin,int end){ int u,v; queue
                 
                   q; for(int i=0;i<=end+2;i++){ pre[i]=-1; vis[i]=0; dist[i]=inf; } vis[begin]=1; dist[begin]=0; q.push(begin); while(!q.empty()){ u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next){ if(edge[i].c>0){ v=edge[i].v; if(dist[v]>dist[u]+edge[i].cost){ dist[v]=dist[u]+edge[i].cost; pre[v]=i; if(!vis[v]){ vis[v]=true; q.push(v); } } } } } return dist[end]!=inf;}int MCMF(int begin,int end){ int ans=0,flow; int flow_sum=0; while(spfa(begin,end)){ flow=inf; for(int i=pre[end];i!=-1;i=pre[edge[i].u]) if(edge[i].c

转载于:https://www.cnblogs.com/markliu/archive/2012/05/22/2513791.html

转载地址：https://blog.csdn.net/weixin_30716141/article/details/95514718 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：利用React遍历数组，并且用数组的元素生成<li>arrItem</li>标签组

下一篇：关于ie获取不到session问题，情况之一

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章