首页 > 代码库 > （二分最大流） 最大流 + 二分查找 小结
（二分最大流） 最大流 + 二分查找 小结
做最大流题目的时候会遇到一种需要用二分查找的题型：
(poj2455) 一张无向图中有 N 个点，M 条边，每条边都有一个权值，且每条边只能用一次，要求找出 T 条从 1 到 N 的路径，使这 T 条路径所经过的边中，权值的最大值最小。
转化为最大流模型：T就是最大流，每条边只能用一次在网络流中就是容量为1。然后二分查找（枚举），边权小于或等于mid的边就加一条容量为1的网络流的边。最后知道最大流ans与T相等的最小的mid就是所求。
在二分查找的时候，与一般的二分查找还是有区别的，一般不能有“ if(ans==T) break;” 这样的语句，因为这种语句使用的条件是函数严格递增,但是我们遇到的题目中很可能会有相邻的函数值相等的情况。
一般情况下，二分写成这样：
while(a<=b) { c=(a+b)/2; …… if(ans>=sum) {res=c;b=c-1;} else a=c+1; }
res就是我们所求的答案。
其实这种题型的建图还是有套路可以找的，多做些题目就有思路了。
hdu3081 Marriage Match II 第一次做这种类型的题目可能会没思路。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=220; 7 const int M=200000, INF=0x3f3f3f3f; 8 struct node 9 { 10 int to,next,w; 11 }edge[M]; 12 int head[N],numh[N],h[N],cure[N],pre[N],f[N],vis[N][N]; 13 int ans,tot,mid; 14 void SAP(int s, int e,int n) 15 { 16 int flow,u,tmp,neck,i; 17 ans=0; 18 memset(pre,-1,sizeof(pre)); 19 memset(h,0,sizeof(h)); 20 memset(numh,0,sizeof(numh)); 21 for(i=1;i<=n;i++) 22 cure[i]=head[i]; 23 numh[0]=n; 24 u=s; 25 while(h[s]<n) 26 { 27 if(u==e) 28 { 29 flow =INF; 30 for(i=s;i!=e;i=edge[cure[i]].to) 31 { 32 if(flow>edge[cure[i]].w) 33 { 34 neck=i; 35 flow =edge[cure[i]].w; 36 } 37 } 38 for(i=s;i!=e;i=edge[cure[i]].to) 39 { 40 tmp=cure[i]; 41 edge[tmp].w-=flow; 42 edge[tmp^1].w+=flow; 43 } 44 ans+=flow; 45 u=neck; 46 } 47 for(i=cure[u];i!=-1;i=edge[i].next) 48 if(edge[i].w && h[u]==h[edge[i].to]+1) break; 49 if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;} 50 else 51 { 52 if(0==--numh[h[u]]) break; //GAPÓÅ»¯ 53 cure[u]=head[u]; 54 for(tmp=n,i=head[u];i!=-1;i=edge[i].next) 55 if(edge[i].w) tmp=min(tmp, h[edge[i].to]); 56 h[u]=tmp+1; 57 ++numh[h[u]]; 58 if(u!=s) u=pre[u]; 59 } 60 } 61 } 62 void addedge(int i,int j,int w) 63 { 64 edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++; 65 edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++; 66 } 67 int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);} 68 void Link(int x,int y) 69 { 70 int a=Find(x),b=Find(y); 71 if(a!=b) {f[b]=a;} 72 } 73 int B[M],G[M]; 74 int main() 75 { 76 //freopen("test.txt","r",stdin); 77 int cas,i,j,k,n,m,x,y,s,e,d,a,b; 78 scanf("%d",&cas); 79 while(cas--) 80 { 81 scanf("%d%d%d",&n,&m,&d); 82 for(i=1;i<=n;i++) f[i]=i; 83 s=2*n+1;e=s+1; 84 for(k=1;k<=m;k++) 85 scanf("%d%d",&G[k],&B[k]); 86 while(d--) 87 { 88 scanf("%d%d",&x,&y); 89 Link(x,y); 90 } 91 x=0,y=n; 92 while(x<=y) 93 { 94 mid=(x+y)/2; 95 tot=0; 96 memset(head,-1,sizeof(head)); 97 memset(vis,0,sizeof(vis)); 98 for(i=1;i<=n;i++){ 99 addedge(s,i,mid);100 addedge(i+n,e,mid);101 }102 for(i=1;i<=m;i++)103 {104 for(j=1;j<=n;j++)105 {106 a=Find(G[i]),b=Find(j);107 if(a==b&&!vis[j][B[i]]) {addedge(j,B[i]+n,1);108 vis[j][B[i]]=1;}109 }110 }111 SAP(s,e,e);112 if(ans>=n*mid) {d=mid;x=mid+1;}113 else y=mid-1;114 }115 printf("%d\n",d);116 }117 return 0;118 }
hdu3277 Marriage Match III 与上面一题类似，多了拆点。拆点可以认为是把有N种属性的物品当为N个物品，但是他们之间还是有联系的。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int N=800; 8 const int M=1100000, INF=10000000; 9 struct node 10 { 11 int to,next,w; 12 }edge[M]; 13 int head[N],numh[N],h[N],cure[N],pre[N]; 14 int ans,n,tot; 15 int f[N],G[M],B[M],mat[N][N]; 16 void SAP(int s, int e,int n) 17 { 18 int flow,u,tmp,neck,i; 19 ans=0; 20 memset(pre,-1,sizeof(pre)); 21 memset(h,0,sizeof(h)); 22 memset(numh,0,sizeof(numh)); 23 for(i=1;i<=n;i++) 24 cure[i]=head[i]; 25 numh[0]=n; 26 u=s; 27 while(h[s]<n) 28 { 29 if(u==e) 30 { 31 flow =INF; 32 for(i=s;i!=e;i=edge[cure[i]].to) 33 { 34 if(flow>edge[cure[i]].w) 35 { 36 neck=i; 37 flow =edge[cure[i]].w; 38 } 39 } 40 for(i=s;i!=e;i=edge[cure[i]].to) 41 { 42 tmp=cure[i]; 43 edge[tmp].w-=flow; 44 edge[tmp^1].w+=flow; 45 } 46 ans+=flow; 47 u=neck; 48 } 49 for(i=cure[u];i!=-1;i=edge[i].next) 50 if(edge[i].w && h[u]==h[edge[i].to]+1) break; 51 if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;} 52 else 53 { 54 if(0==--numh[h[u]]) break; //GAPÓÅ»¯ 55 cure[u]=head[u]; 56 for(tmp=n,i=head[u];i!=-1;i=edge[i].next) 57 if(edge[i].w) tmp=min(tmp, h[edge[i].to]); 58 h[u]=tmp+1; 59 ++numh[h[u]]; 60 if(u!=s) u=pre[u]; 61 } 62 } 63 } 64 void init() 65 { 66 for(int i=1;i<N;i++) f[i]=i; 67 memset(mat,0,sizeof(mat)); 68 } 69 void addedge(int i,int j,int w) 70 { 71 edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++; 72 edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++; 73 } 74 int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);} 75 void Link(int x,int y) 76 { 77 int a=Find(x),b=Find(y); 78 if(a!=b) f[b]=a; 79 } 80 int main() 81 { 82 //freopen("test.txt","r",stdin); 83 int m,n,f,i,j,k,cas,s,e; 84 scanf("%d",&cas); 85 while(cas--) 86 { 87 scanf("%d%d%d%d",&n,&m,&k,&f); 88 init(); 89 s=3*n+1; e=s+1; 90 for(i=1;i<=m;i++) 91 { 92 scanf("%d%d",&G[i],&B[i]); 93 } 94 while(f--) 95 { 96 scanf("%d%d",&i,&j); 97 Link(i,j); 98 } 99 for(i=1;i<=m;i++)100 {101 int g=Find(G[i]);102 mat[g][B[i]]=1;103 }104 int a=0,b=n,mid;105 while(a<=b)106 {107 mid=(a+b)/2;108 tot=0;109 memset(head,-1,sizeof(head));110 for(i=1;i<=n;i++)111 {112 addedge(s,i,mid);113 addedge(i,i+n,k);114 addedge(2*n+i,e,mid);115 }116 for(i=1;i<=n;i++)117 {118 for(j=1;j<=n;j++)119 {120 if(mat[Find(i)][j]) addedge(i,j+2*n,1);121 else addedge(i+n,j+2*n,1);122 }123 }124 SAP(s,e,e);125 if(ans>=n*mid) {a=mid+1;f=mid;}126 else b=mid-1;127 }128 printf("%d\n",f);129 }130 return 0;131 }
poj2112 Optimal Milking 这种类型的基本题。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N =250, M=100000,INF=0x3f3f3f3f; 7 int Map[N][N], dist[N][N], pre[N]; 8 void floyd(int n) 9 { 10 int i,j,k; 11 for(i=1;i<=n;i++) 12 { 13 for(j=1;j<=n;j++) 14 { 15 dist[i][j]=Map[i][j]; 16 } 17 } 18 for(k=1;k<=n;k++) 19 for(i=1;i<=n;i++) 20 for(j=1;j<=n;j++) 21 if(dist[i][k]!=INF&&dist[k][j]!=INF&& 22 dist[i][k]+dist[k][j]<dist[i][j]) 23 { 24 dist[i][j]=dist[i][k]+ dist[k][j]; 25 } 26 } 27 struct node 28 { 29 int to,next,w; 30 }edge[M]; 31 int head[N],numh[N],h[N],cure[N]; 32 int ans,tot; 33 void SAP(int s, int e,int n) 34 { 35 int flow,u,tmp,neck,i; 36 ans=0; 37 for(i=1;i<=n;i++) 38 cure[i]=head[i]; 39 numh[0]=n; 40 u=s; 41 while(h[s]<n) 42 { 43 if(u==e) 44 { 45 flow =INF; 46 for(i=s;i!=e;i=edge[cure[i]].to) 47 { 48 if(flow>edge[cure[i]].w) 49 { 50 neck=i; 51 flow =edge[cure[i]].w; 52 } 53 } 54 for(i=s;i!=e;i=edge[cure[i]].to) 55 { 56 tmp=cure[i]; 57 edge[tmp].w-=flow; 58 edge[tmp^1].w+=flow; 59 } 60 ans+=flow; 61 u=neck; 62 } 63 for(i=cure[u];i!=-1;i=edge[i].next) 64 if(edge[i].w && h[u]==h[edge[i].to]+1) break; 65 if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;} 66 else 67 { 68 if(0==--numh[h[u]]) break; //GAPÓÅ»¯ 69 cure[u]=head[u]; 70 for(tmp=n,i=head[u];i!=-1;i=edge[i].next) 71 if(edge[i].w) tmp=min(tmp, h[edge[i].to]); 72 h[u]=tmp+1; 73 ++numh[h[u]]; 74 if(u!=s) u=pre[u]; 75 } 76 } 77 } 78 void init() 79 { 80 tot=0; 81 memset(head,-1,sizeof(head)); 82 memset(pre,-1,sizeof(pre)); 83 memset(h,0,sizeof(h)); 84 memset(numh,0,sizeof(numh)); 85 86 } 87 void addedge(int i,int j,int w) 88 { 89 edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++; 90 edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++; 91 } 92 int main() 93 { 94 //freopen("test.txt","r",stdin); 95 int k,c,m,i,j,t,s,e,n,R,L,mid; 96 while(scanf("%d%d%d",&k,&c,&m)!=EOF) 97 { 98 n=k+c; 99 for(i=1;i<=n;i++)100 for(j=1;j<=n;j++)101 {102 Map[i][j]=INF;103 scanf("%d",&t);104 if(i==j) continue;105 if(t!=0) Map[i][j]=t;106 }107 floyd(n);108 R=L=0;109 for(i=1;i<=n;i++)110 for(j=1;j<=n;j++)111 if(dist[i][j]!=INF) R=max(R,dist[i][j]);112 s=n+1;e=s+1;113 while(L<=R)114 {115 mid=(R+L)/2;116 init();117 for(i=1;i<=k;i++) addedge(s,i,m);118 for(i=1;i<=c;i++) addedge(i+k,e,1);119 for(i=1;i<=k;i++)120 for(j=k+1;j<=n;j++)121 if(dist[i][j]<=mid) addedge(i,j,1);122 SAP(s,e,e);123 if(ans>=c) R=mid-1,t=mid;124 else L=mid+1;125 }126 printf("%d\n",t);127 }128 return 0;129 }
poj3228 Gold Transportation
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int N=410; 8 const int M=100000, INF=0x3f3f3f3f; 9 struct node 10 { 11 int to,next,w; 12 }edge[M]; 13 int head[N],numh[N],h[N],cure[N],pre[N]; 14 int ans,tot; 15 void SAP(int s, int e,int n) 16 { 17 int flow,u,tmp,neck,i; 18 ans=0; 19 for(i=1;i<=n;i++) 20 cure[i]=head[i]; 21 numh[0]=n; 22 u=s; 23 while(h[s]<n) 24 { 25 if(u==e) 26 { 27 flow =INF; 28 for(i=s;i!=e;i=edge[cure[i]].to) 29 { 30 if(flow>edge[cure[i]].w) 31 { 32 neck=i; 33 flow =edge[cure[i]].w; 34 } 35 } 36 for(i=s;i!=e;i=edge[cure[i]].to) 37 { 38 tmp=cure[i]; 39 edge[tmp].w-=flow; 40 edge[tmp^1].w+=flow; 41 } 42 ans+=flow; 43 u=neck; 44 } 45 for(i=cure[u];i!=-1;i=edge[i].next) 46 if(edge[i].w && h[u]==h[edge[i].to]+1) break; 47 if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;} 48 else 49 { 50 if(0==--numh[h[u]]) break; //GAP优化 51 cure[u]=head[u]; 52 for(tmp=n,i=head[u];i!=-1;i=edge[i].next) 53 if(edge[i].w) tmp=min(tmp, h[edge[i].to]); 54 h[u]=tmp+1; 55 ++numh[h[u]]; 56 if(u!=s) u=pre[u]; 57 } 58 } 59 } 60 void init() 61 { 62 tot=0; 63 memset(head,-1,sizeof(head)); 64 memset(pre,-1,sizeof(pre)); 65 memset(h,0,sizeof(h)); 66 memset(numh,0,sizeof(numh)); 67 68 } 69 void addedge(int i,int j,int w) 70 { 71 edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++; 72 edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++; 73 } 74 struct ND 75 { 76 int u,v,w; 77 }e[M]; 78 int g[N],p[N]; 79 int main() 80 { 81 //freopen("test.txt","r",stdin); 82 int n,m,i,j,k,s,E,a,b,c,sum,res,s1; 83 while(scanf("%d",&n)!=EOF) 84 { 85 if(!n) break; 86 sum=0;s1=0; 87 for(i=1;i<=n;i++) {scanf("%d",&g[i]); sum+=g[i]; } 88 for(i=1;i<=n;i++) {scanf("%d",&p[i]); s1+=p[i];} 89 scanf("%d",&m); 90 a=INF; b=0; 91 int t=0; 92 while(m--){ 93 scanf("%d%d%d",&i,&j,&k); 94 e[t].u=i;e[t].v=j;e[t].w=k;t++; 95 a=min(a,k); b=max(b,k); 96 } 97 if(sum>s1) {printf("No Solution\n");continue;} 98 s=n+1; E=s+1;res=-1; 99 while(a<=b)100 {101 c=(a+b)/2;102 init();103 for(i=1;i<=n;i++)104 {105 if(g[i])addedge(s,i,g[i]);106 if(p[i])addedge(i,E,p[i]);107 }108 for(i=0;i<t;i++)109 if(e[i].w<=c) addedge(e[i].u,e[i].v,INF),addedge(e[i].v,e[i].u,INF);110 SAP(s,E,E);111 if(ans>=sum) {res=c;b=c-1;}112 else a=c+1;113 }114 if(res==-1) printf("No Solution\n");115 else printf("%d\n",res);116 }117 return 0;118 }
poj2455 Secret Milking Machine
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=210; 7 const int M=100000, INF=0x3f3f3f3f; 8 struct node 9 { 10 int to,next,w; 11 }edge[M]; 12 struct ND 13 { 14 int u,v,w; 15 }e[40010]; 16 int head[N],numh[N],h[N],cure[N],pre[N]; 17 int ans,tot; 18 void SAP(int s, int e,int n) 19 { 20 int flow,u,tmp,neck,i; 21 ans=0; 22 for(i=1;i<=n;i++) 23 cure[i]=head[i]; 24 numh[0]=n; 25 u=s; 26 while(h[s]<n) 27 { 28 if(u==e) 29 { 30 flow =INF; 31 for(i=s;i!=e;i=edge[cure[i]].to) 32 { 33 if(flow>edge[cure[i]].w) 34 { 35 neck=i; 36 flow =edge[cure[i]].w; 37 } 38 } 39 for(i=s;i!=e;i=edge[cure[i]].to) 40 { 41 tmp=cure[i]; 42 edge[tmp].w-=flow; 43 edge[tmp^1].w+=flow; 44 } 45 ans+=flow; 46 u=neck; 47 } 48 for(i=cure[u];i!=-1;i=edge[i].next) 49 if(edge[i].w && h[u]==h[edge[i].to]+1) break; 50 if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;} 51 else 52 { 53 if(0==--numh[h[u]]) break; //GAP优化 54 cure[u]=head[u]; 55 for(tmp=n,i=head[u];i!=-1;i=edge[i].next) 56 if(edge[i].w) tmp=min(tmp, h[edge[i].to]); 57 h[u]=tmp+1; 58 ++numh[h[u]]; 59 if(u!=s) u=pre[u]; 60 } 61 } 62 } 63 void init() 64 { 65 tot=0; 66 memset(head,-1,sizeof(head)); 67 memset(pre,-1,sizeof(pre)); 68 memset(h,0,sizeof(h)); 69 memset(numh,0,sizeof(numh)); 70 } 71 void addedge(int i,int j,int w) 72 { 73 edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++; 74 edge[tot].to=i;edge[tot].w=w;edge[tot].next=head[j];head[j]=tot++; 75 } 76 bool cmp(const ND &a, const ND &b) 77 { 78 return a.w<b.w; 79 } 80 int main() 81 { 82 //freopen("test.txt","r",stdin); 83 int n,p,T,i,j,k,R,L,m,s; 84 scanf("%d%d%d",&n,&p,&T); 85 R=0;L=INF; 86 for(i=0;i<p;i++) 87 { 88 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); 89 k=e[i].w; 90 R=max(R,k); 91 L=min(L,k); 92 } 93 sort(e,e+p,cmp); 94 while(L<=R) 95 { 96 init(); 97 m=(L+R)/2; 98 for(i=0;i<p;i++) 99 {100 if(e[i].w>m)break;101 addedge(e[i].u,e[i].v,1);102 }103 SAP(1,n,n);104 if(ans>=T) {s=m; R=m-1;}105 else L=m+1;106 }107 printf("%d\n",m);108 return 0;109 }
poj2391 Ombrophobic Bovines
此题是这种类型中较难的题目，综合性挺高的。需要用floyd求任意两点之间的最短距离，然后二分查找。最烦的是超出了int范围，需要修改好几处。并且最不顺心的是习惯上用的二分查找在这里过不了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N =500,M=1000000; 7 const long long INF=0x3f3f3f3f3f3f; 8 long long Map[N][N], dist[N][N],ans; 9 void floyd(int n) 10 { 11 int i,j,k; 12 for(i=1;i<=n;i++) 13 { 14 for(j=1;j<=n;j++) 15 { 16 dist[i][j]=Map[i][j]; 17 } 18 } 19 for(k=1;k<=n;k++) 20 for(i=1;i<=n;i++) 21 for(j=1;j<=n;j++) 22 if(dist[i][k]!=INF&&dist[k][j]!=INF&& 23 dist[i][k]+dist[k][j]<dist[i][j]) 24 { 25 dist[i][j]=dist[i][k]+ dist[k][j]; 26 } 27 } 28 struct node 29 { 30 int to,next,w; 31 }edge[M]; 32 int head[N],numh[N],h[N],cure[N],pre[N]; 33 int tot; 34 void SAP(int s, int e,int n) 35 { 36 int u,tmp,neck,i; 37 long long flow; 38 ans=0; 39 for(i=1;i<=n;i++) 40 cure[i]=head[i]; 41 numh[0]=n; 42 u=s; 43 while(h[s]<n) 44 { 45 if(u==e) 46 { 47 flow =INF; 48 for(i=s;i!=e;i=edge[cure[i]].to) 49 { 50 if(flow>edge[cure[i]].w) 51 { 52 neck=i; 53 flow =edge[cure[i]].w; 54 } 55 } 56 for(i=s;i!=e;i=edge[cure[i]].to) 57 { 58 tmp=cure[i]; 59 edge[tmp].w-=flow; 60 edge[tmp^1].w+=flow; 61 } 62 ans+=flow; 63 u=neck; 64 } 65 for(i=cure[u];i!=-1;i=edge[i].next) 66 if(edge[i].w && h[u]==h[edge[i].to]+1) break; 67 if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;} 68 else 69 { 70 if(0==--numh[h[u]]) break; //GAP优化 71 cure[u]=head[u]; 72 for(tmp=n,i=head[u];i!=-1;i=edge[i].next) 73 if(edge[i].w) tmp=min(tmp, h[edge[i].to]); 74 h[u]=tmp+1; 75 ++numh[h[u]]; 76 if(u!=s) u=pre[u]; 77 } 78 } 79 } 80 void init() 81 { 82 tot=0; 83 memset(head,-1,sizeof(head)); 84 memset(pre,-1,sizeof(pre)); 85 memset(h,0,sizeof(h)); 86 memset(numh,0,sizeof(numh)); 87 88 } 89 void addedge(int i,int j,int w) 90 { 91 edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++; 92 edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++; 93 } 94 int c[N],x[N]; 95 int main() 96 { 97 //freopen("test.txt","r",stdin); 98 int n,m,i,j,k; 99 long long res,L,R,mid,s1,s2,w;100 while(scanf("%d%d",&n,&m)!=EOF){101 for(i=1;i<=n;i++)102 {103 Map[i][i]=0;104 for(j=i+1;j<=n;j++)105 Map[j][i]=Map[i][j]=INF;106 }107 s1=s2=0;108 for(i=1;i<=n;i++)109 {110 scanf("%d%d",&x[i],&c[i]);111 s1+=x[i];s2+=c[i];112 }113 114 while(m--)115 {116 scanf("%d%d%I64d",&i,&j,&w);117 Map[i][j]=Map[j][i]=min(w,Map[i][j]);118 }119 if(s1>s2) {printf("-1\n");continue;}120 for(i=1;i<=n;i++)121 if(x[i]>c[i]) break;122 if(i>n) {printf("0\n");continue;}123 floyd(n);124 int s=2*n+1,e=s+1;125 L=0,res=-1,R=INF;126 while(L<R)127 {128 init();129 mid=(R+L)/2;130 for(i=1;i<=n;i++)131 {132 addedge(i,i+n,INF);133 addedge(s,i,x[i]);134 addedge(i+n,e,c[i]);135 for(j=1;j<=n;j++)136 {137 if(i==j) continue;138 if(dist[i][j]<=mid) addedge(i,j+n,INF);139 }140 }141 SAP(s,e,e);142 if(ans>=s1) {res=mid; R=mid;}143 else L=mid+1;144 }145 printf("%I64d\n",res);146 }147 return 0;148 }
我的代码中最大流算法都是用的优化的SAP算法，因为他的时间复杂度低。并且我已经习惯了这代码。
SAP模版：
1 const int N=110; 2 const int M=2*N*N, INF=0x3f3f3f3f; 3 struct node 4 { 5 int to,next,w; 6 }edge[M]; 7 int head[N],numh[N],h[N],cure[N],pre[N]; 8 int ans,tot; 9 void SAP(int s, int e,int n)10 {11 int flow,u,tmp,neck,i;12 ans=0;13 for(i=1;i<=n;i++)14 cure[i]=head[i];15 numh[0]=n;16 u=s;17 while(h[s]<n)18 {19 if(u==e)20 {21 flow =INF;22 for(i=s;i!=e;i=edge[cure[i]].to)23 {24 if(flow>edge[cure[i]].w)25 {26 neck=i;27 flow =edge[cure[i]].w;28 }29 }30 for(i=s;i!=e;i=edge[cure[i]].to)31 {32 tmp=cure[i];33 edge[tmp].w-=flow;34 edge[tmp^1].w+=flow;35 }36 ans+=flow;37 u=neck;38 }39 for(i=cure[u];i!=-1;i=edge[i].next)40 if(edge[i].w && h[u]==h[edge[i].to]+1) break;41 if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;}42 else43 {44 if(0==--numh[h[u]]) break; //GAP优化45 cure[u]=head[u];46 for(tmp=n,i=head[u];i!=-1;i=edge[i].next)47 if(edge[i].w) tmp=min(tmp, h[edge[i].to]);48 h[u]=tmp+1;49 ++numh[h[u]];50 if(u!=s) u=pre[u];51 }52 }53 }54 void init()55 {56 tot=0;57 memset(head,-1,sizeof(head));58 memset(pre,-1,sizeof(pre));59 memset(h,0,sizeof(h));60 memset(numh,0,sizeof(numh));61 62 }63 void addedge(int i,int j,int w)64 {65 edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++;66 edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++;67 }
（二分最大流） 最大流 + 二分查找 小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。