[BZOJ3698]XWW的難題（有源匯有上下界的最大流）

2019-11-14 12:39:24

字體：大中小

供稿：網(wǎng)友

題目描述

傳送門

題解

最大流和可行流的做法的區(qū)別：先ss->tt做一遍最大流，判斷是否可行；然后將t->s,inf這條邊去掉，再做一遍s->t的最大流，即為答案這道題原圖的建圖方法是：對(duì)于每一行i，s->i,[a(i,n),a(i,n)+1] 對(duì)于每一列j，j->t,[a(n,j),a(n,j)+1] 對(duì)于每一個(gè)點(diǎn)(i,j)，i->j,[a(i,j),a(i,j)+1] 然后再按照有源匯有上下界對(duì)這個(gè)圖進(jìn)行改造即可

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<queue>using namespace std;#define N 100005#define inf 1000000000int n,s,t,ss,tt,maxflow,in,out,ans;double a[105][105];int l[105][105],r[105][105],p[105][105];int tot,point[N],nxt[N],v[N],remain[N];int d[N],deep[N],last[N],cur[N],num[N];queue <int> q;void addedge(int x,int y,int cap){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=cap; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0;}void bfs(int t){ for (int i=1;i<=t;++i) deep[i]=t; deep[t]=0; for (int i=1;i<=t;++i) cur[i]=point[i]; while (!q.empty()) q.pop(); q.push(t); while (!q.empty()) { int now=q.front();q.pop(); for (int i=point[now];i!=-1;i=nxt[i]) if (deep[v[i]]==t&&remain[i^1]) { deep[v[i]]=deep[now]+1; q.push(v[i]); } }}int addflow(int s,int t){ int now=t,ans=inf; while (now!=s) { ans=min(ans,remain[last[now]]); now=v[last[now]^1]; } now=t; while (now!=s) { remain[last[now]]-=ans; remain[last[now]^1]+=ans; now=v[last[now]^1]; } return ans;}void isap(int s,int t){ bfs(t); for (int i=1;i<=t;++i) ++num[deep[i]]; int now=s; while (deep[s]<t) { if (now==t) { maxflow+=addflow(s,t); now=s; } bool has_find=false; for (int i=cur[now];i!=-1;i=nxt[i]) if (deep[v[i]]+1==deep[now]&&remain[i]) { has_find=true; cur[now]=i; last[v[i]]=i; now=v[i]; break; } if (!has_find) { int minn=t-1; for (int i=point[now];i!=-1;i=nxt[i]) if (remain[i]) minn=min(minn,deep[v[i]]); if (!(--num[deep[now]])) break; ++num[deep[now]=minn+1]; cur[now]=point[now]; if (now!=s) now=v[last[now]^1]; } }}int main(){ tot=-1;memset(point,-1,sizeof(point)); scanf("%d",&n); for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) { scanf("%lf",&a[i][j]); l[i][j]=floor(a[i][j]); r[i][j]=ceil(a[i][j]); } s=n+n+1,t=s+1,ss=t+1,tt=ss+1; for (int i=1;i<n;++i) { addedge(s,i,r[i][n]-l[i][n]); d[s]-=l[i][n],d[i]+=l[i][n]; addedge(n+i,t,r[n][i]-l[n][i]); d[n+i]-=l[n][i],d[t]+=l[n][i]; } for (int i=1;i<n;++i) for (int j=1;j<n;++j) { addedge(i,n+j,r[i][j]-l[i][j]); p[i][j]=tot; d[i]-=l[i][j],d[n+j]+=l[i][j]; } for (int i=1;i<=t;++i) { if (d[i]>0) addedge(ss,i,d[i]),in+=d[i]; if (d[i]<0) addedge(i,tt,-d[i]),out-=d[i]; } addedge(t,s,inf); if (in!=out) {puts("NO");return 0;} isap(ss,tt); if (maxflow!=in) {puts("NO");return 0;} remain[tot]=remain[tot^1]=0; isap(s,t); for (int i=1;i<n;++i) for (int j=1;j<n;++j) ans+=remain[p[i][j]]+l[i][j];