poj 3469

本文主要是介绍poj 3469，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

       这道题是用解决最大流问题的Dinic算法写的，由于题目数据量较大，所以要选择较为高效的算法。

       这道题应该算一种经典的题型，用最小费用将对象分成两个集合的问题，利用最大流最小割定理来解决。通过构图，使得最小费用等于最小割的容量，从而通过最大流算法求出最小割的容量，也即为最小的费用。

       就这道题而言，N个模块作为N个点，与源点有容量为B的弧，与汇点有容量为A的弧，如果a，b两点在不同的CPU核上工作有额外的费用，则在从a连一条容量为w指向b的弧，连一条同样容量由b到a的弧。构好图，接下来就是求最大流最小割的问题。

代码（C++）：

#include <cstdlib>
#include <iostream>
#include <queue>
#include <algorithm>#define MAX 20050
#define INF (1<<30)
using namespace std;//#define LOCALstruct Edge{int v;int cap;int next;   
} edge[MAX*10*2*2+MAX*4];int head[MAX],c,level[MAX];void add_edge(int u,int v,int cap)
{edge[c].v=v;edge[c].cap=cap;edge[c].next=head[u];head[u]=c;c++;edge[c].v=u;edge[c].cap=0;edge[c].next=head[v];head[v]=c;c++; 
}void bfs(int s)
{int u,v,i;queue<int> qi;level[s]=0;qi.push(s);while(!qi.empty()){u=qi.front();qi.pop();for(i=head[u];i!=-1;i=edge[i].next){v=edge[i].v;                          if(edge[i].cap>0&&level[v]==-1){               level[v]=level[u]+1;qi.push(v);             }                              }              }
}int dfs(int u,int t,int f)
{int i,v,d,res;if(u==t) return f;res=0;for(i=head[u];i!=-1;i=edge[i].next){v=edge[i].v;                              if(edge[i].cap>0&&level[v]==level[u]+1) {d=dfs(v,t,min(edge[i].cap,f-res));  if(d>0){edge[i].cap-=d;edge[i^1].cap+=d; res+=d;if(res==f) return res;   }               }                             }return res;
}int dinic(int s,int t)
{int flow;flow=0;while(1){memset(level,-1,sizeof(level));bfs(s);if(level[t]==-1) return flow;flow+=dfs(s,t,INF); }
}int main(int argc, char *argv[])
{
#ifdef LOCALfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endifint n,m,a,b,w,i;while(scanf("%d %d",&n,&m)!=EOF)//超级源点：0    超级汇点：n+1    模块：1~n {c=0;            memset(head,-1,sizeof(head));            for(i=1;i<=n;i++){scanf("%d %d",&a,&b);add_edge(0,i,b);add_edge(i,n+1,a);             } for(i=0;i<m;i++){scanf("%d %d %d",&a,&b,&w);add_edge(a,b,w);add_edge(b,a,w);            }  printf("%d\n",dinic(0,n+1));         }system("PAUSE");return EXIT_SUCCESS;
}

题目（ http://poj.org/problem?id=3469）：

Description

Input

Output

Sample Input

3 1
1 10
2 10
10 3
2 3 1000

Sample Output

13

这篇关于poj 3469的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---