最大流(BZOJ1313)

#include <cstdio> #include <cstring> #include <cmath> #define LDB long double using namespace std;int cnt,nd[10001],dep[10001],sor,tar,dl[10001],n,cur[10001],sta[1000001];LDB a[101][101];int in[10001],tot;struct edge{int next,des,cap,fr;}sid[1000001];void addedge(int u,int v,int cap){sid[cnt].next=nd[u];sid[cnt].des=v;sid[cnt].cap=cap;nd[u]=cnt;sid[cnt].fr=u;cnt++;sid[cnt].next=nd[v];sid[cnt].des=u;sid[cnt].cap=0;nd[v]=cnt;sid[cnt].fr=v;cnt++;}int bfs(){memset(dep,-1,sizeof(dep));int head=1,tail=1;dep[sor]=0;dl[head]=sor;while (head<=tail){for (int p=nd[dl[head]];p!=-1;p=sid[p].next)if ((dep[sid[p].des]==-1)&&(sid[p].cap)) dep[sid[p].des]=dep[dl[head]]+1,dl[++tail]=sid[p].des;head++; }if (dep[tar]==-1) return(0);else return(1);}int dinic(){int maxflow=0;while (bfs()){for (int i=0;i<=2*n+1;i++) cur[i]=nd[i];int u=sor,top=0;while(1){if (u==tar){int mi=1e9,last;for (int i=1;i<=top;i++)if (sid[sta[i]].cap<mi){mi=sid[sta[i]].cap;last=i;}for (int i=1;i<=top;i++) sid[sta[i]].cap-=mi,sid[sta[i]^1].cap+=mi;u=sid[sta[last]].fr;cur[u]=sid[cur[u]].next;top=last-1;maxflow+=mi;continue;}while((cur[u]!=-1)&&((sid[cur[u]].cap==0)||(dep[sid[cur[u]].des]!=dep[u]+1)))cur[u]=sid[cur[u]].next;if (cur[u]!=-1){sta[++top]=cur[u];u=sid[cur[u]].des;continue;}else{if (u==sor) break;dep[u]=-1;u=sid[sta[top--]].fr;continue;} }}return(maxflow);}void build(){for (int i=1;i<n;i++){if (fabs(a[i][n]-(int)a[i][n])>1e-3) addedge(0,i,1);in[0]-=(int)a[i][n];in[i]+=(int)a[i][n]; }for (int i=1;i<n;i++){if (fabs(a[n][i]-(int)a[n][i])>1e-3) addedge(i+n-1,2*n-1,1);in[i+n-1]-=(int)a[n][i];in[2*n-1]+=(int)a[n][i];}for (int i=1;i<n;i++)for (int j=1;j<n;j++){if (fabs(a[i][j]-(int)a[i][j])>1e-3) addedge(i,n-1+j,1);in[i]-=(int)a[i][j];in[n-1+j]+=(int)a[i][j];}for (int i=0;i<=2*n-1;i++)if (in[i]>0) {tot+=in[i];addedge(2*n,i,in[i]);}elseif (in[i]<0) addedge(i,2*n+1,-in[i]); }int main(){ scanf("%d",&n);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)scanf("%Lf",&a[i][j]);for (int i=0;i<=2*n+1;i++) nd[i]=-1; build();sor=2*n;tar=2*n+1;addedge(2*n-1,0,1e9);if (dinic()!=tot) {printf("No\n");return(0);}sor=0;tar=2*n-1;printf("%d\n",3*dinic()); }

?

轉載于:https://www.cnblogs.com/zhujiangning/p/6221315.html

總結

以上是生活随笔為你收集整理的上下界网络流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。