POJ 1459 & ZOJ 1734 Power Network (网络最大流) - c++编程基础

TOP

POJ 1459 & ZOJ 1734 Power Network (网络最大流)(二)

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

Tags：POJ 1459 & ZOJ 1734 Power Network 网络最大

]=fir[u[e]];fir[u[e]]=e; } int max_flow(int s,int t) { memset(flow,0,sizeof flow); int total_flow=0; for (;;) { memset(d,0,sizeof d); d[s]=INF; int f=0,r=0; q[0]=s; while (f<=r) { int _u=q[f++]; for (int e=fir[_u];~e;e=nex[e]) { if (!d[v[e]] && cap[e]>flow[e]) { q[++r]=v[e]; p[v[e]]=e; d[v[e]]=min(d[u[e]],cap[e]-flow[e]); } } } if (d[t]==0) break; for (int e=p[t];;e=p[u[e]]) { flow[e]+=d[t]; flow[e^1]-=d[t]; if (u[e]==s) break; } total_flow+=d[t]; } return total_flow; } int main() { #ifndef ONLINE_JUDGE freopen(/home/fcbruce/文档/code/t,r,stdin); #endif // ONLINE_JUDGE int n,np,nc,m,_u,_v,_w; while (~scanf(%d %d %d %d,&n,&np,&nc,&m)) { e_max=0; int s=n,t=n+1; memset(fir,-1,sizeof fir); for (int i=0;i

dinic算法实现：

#include
                   
                    
#include
                    
                      #include
                     
                       #include
                      
                        #include
                       
                         #include
                        
                          #include
                         
                           #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 13000 #define maxn 300 using namespace std; int G[maxn][maxn]; int fir[maxn]; int u[maxm],v[maxm],cap[maxm],flow[maxm],nex[maxm]; int e_max; int lv[maxn],iter[maxn]; int q[maxm]; 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); q[f=r=0]=s; lv[s]=0; 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]
                                  
                                   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 iter); int _f; while ((_f=dinic_dfs(s,t,INF))>0) total_flow+=_f; } return total_flow; } int main() { #ifndef ONLINE_JUDGE freopen(/home/fcbruce/文档/code/t,r,stdin); #endif // ONLINE_JUDGE int l=INF,r=0,K,C,M; scanf(%d %d %d,&K,&C,&M); for (int i=1;i<=K+C;i++) for (int j=1;j<=K+C;j++) scanf(%d,&G[i][j]),G[i][j]=G[i][j]?G[i][j]:INF; for (int k=1;k<=K+C;k++) for (int i=1;i<=K+C;i++) for (int j=1;j<=K+C;j++) G[i][j]=min(G[i][k]+G[k][j],G[i][j]); int ans=-1; // printf(%d %d ,l,r); l=0;r=INF; while (l<=r) { int mid=l+r>>1; e_max=0; memset(fir,-1,sizeof fir); for (int i=K+1;i<=K+C;i++) add_edge(0,i,1); for (int i=1;i<=K;i++) add_edge(i,K+C+1,M); for (int i=K+1;i<=K+C;i++) for (int j=1;j<=K;j++) if (G[i][j]<=mid) add_edge(i,j,1); // printf(mid=%d ,mid); if (max_flow(0,K+C+1)==C) { ans=mid; r=mid-1; } else { l=mid+1; } } printf(%d ,ans); return 0; }

首页上一页 1 2 下一页尾页 2/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 2761 Feed the dogs	下一篇：uva714 - Copying Books(最大值最..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: