POJ 3436 ACM Computer Factory(网络最大流) - c++编程基础

TOP

POJ 3436 ACM Computer Factory(网络最大流)(二)

2015-07-20 18:00:42 来源: 作者: 【大中小】浏览:6次

#include #include #include #include #include #include #include #include #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #define maxm 210007 #define maxn 107 using namespace std; int fir[maxn]; int u[maxm],v[maxm],cap[maxm],flow[maxm],nex[maxm]; int e_max; int lv[maxn],q[maxn],iter[maxn]; void add_edge(int _u,int _v,int _w) { int e; e=e_max++; u[e]=_u;v[e]=_v;cap[e]=_w;nex[e]=fir[u[e]];fir[u[e]]=e; e=e_max++; u[e]=_v;v[e]=_u;cap[e]=0;nex[e]=fir[u[e]];fir[u[e]]=e; } void dinic_bfs(int s) { int f,r; memset(lv,-1,sizeof lv); lv[s]=0; q[f=r=0]=s; while (f<=r) { int x=q[f++]; for (int e=fir[x];~e;e=nex[e]) { if(cap[e]>flow[e] && lv[v[e]]<0) { lv[v[e]]=lv[u[e]]+1; q[++r]=v[e]; } } } } int dinic_dfs(int _u,int t,int _f) { if (_u==t) return _f; for (int &e=iter[_u];~e;e=nex[e]) { if (cap[e]>flow[e] && lv[u[e]] 0) { flow[e]+=_d; flow[e^1]-=_d; return _d; } } } return 0; } int max_flow(int s,int t) { memset(flow,0,sizeof flow); int total_flow=0; for (;;) { dinic_bfs(s); if (lv[t]<0) return total_flow; memcpy(iter,fir,sizeof fir); int _f; while ((_f=dinic_dfs(s,t,INF))>0) total_flow+=_f; } return total_flow; } struct node { int in[10],out[10]; int in1,out0; }a[55]; int main() { #ifndef ONLINE_JUDGE freopen("/home/fcbruce/文档/code/t","r",stdin); #endif // ONLINE_JUDGE int p,n,s,t,_w; e_max=0; memset(fir,-1,sizeof fir); scanf("%d %d",&p,&n); s=0;t=n+n+1; for (int i=1;i<=n;i++) { scanf("%d",&_w); add_edge(i,i+n,_w); a[i].in1=0; for (int j=0;j n?u[e]-n:u[e]; v[m]=v[e]; flow[m]=flow[e]; m++; } printf("%d\n",m); for (int e=0;e

首页上一页 1 2 下一页尾页 2/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：uva 1521 - GCD Guessing Game(贪..	下一篇：HDU-2128-Tempter of the Bone II..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: