題目大意：

XWW是個(gè)影響力很大的人，他有很多的追隨者。這些追隨者都想要加入XWW教成為XWW的教徒。但是這并不容易，需要通過XWW的考核。
XWW給你出了這么一個(gè)難題：XWW給你一個(gè)N*N的正實(shí)數(shù)矩陣A，滿足XWW性。
稱一個(gè)N*N的矩陣滿足XWW性當(dāng)且僅當(dāng)：（1）A[N][N]=0；（2）矩陣中每行的最后一個(gè)元素等于該行前N-1個(gè)數(shù)的和；（3）矩陣中每列的最后一個(gè)元素等于該列前N-1個(gè)數(shù)的和。
現(xiàn)在你要給A中的數(shù)進(jìn)行取整操作（可以是上取整或者下取整），使得最后的A矩陣仍然滿足XWW性。同時(shí)XWW還要求A中的元素之和盡量大。

思路：

首先這一題的建模還是挺有意思的。每一個(gè)點(diǎn)的取值有一個(gè)范圍，同時(shí)還要要求它們加起來的和要在某一個(gè)范圍之內(nèi)。于是便自然地想到了每一個(gè)點(diǎn)為一條流量然后一起流到一個(gè)管道里然后這個(gè)管道的流量也是有上下界的，模型的大概就這樣建出來了。
但是煩惱了我挺久的就是這題是一個(gè)二維矩陣，對(duì)于每一個(gè)點(diǎn)所代表的流量它既要匯合到它這一橫行，又要匯合到這一豎行，顯然流量是單向流動(dòng)的，并且流量匯合了之后又不可以重新分開成之前沒匯合的一樣，這里想了我很久。
然后就突然想到，為什么一定要匯合呢？在每一行匯合前每一個(gè)格子的流量可以從它的那一列引出來啊，這樣就可以當(dāng)做是每一列拆開成n?1n?1個(gè)流量之后再分別匯到那n?1n?1行去，然后就可以完美地套用有上下界的最大流了。
有上下界的最大流大體上和有上下界的最小流是差不多的，最后的推流只不過是順著推流罷了。

/*============================* Author : ylsoi* Problem : bzoj3698* Algorithm : Max_Flow* Time : 2018.7.29* =========================*/ #include<bits/stdc++.h>#define REP(i,a,b) for(int i=a;i<=b;++i) typedef long long ll;using namespace std;void File(){freopen("bzoj3698.in","r",stdin);freopen("bzoj3698.out","w",stdout); }const int maxn=100+10; const int maxe=1e5+10; const int inf=0x3f3f3f3f; int n,s,t,ss,tt,sumf,ans; int a[maxn][maxn],b[maxn][maxn],c[maxn<<1],sum; int beg[maxn<<1],las[maxe<<1],to[maxe<<1],flow[maxe<<1],cnte=1;void add(int u,int v,int f){las[++cnte]=beg[u]; beg[u]=cnte; to[cnte]=v; flow[cnte]=f;las[++cnte]=beg[v]; beg[v]=cnte; to[cnte]=u; flow[cnte]=0; }struct dinic{int num[maxn<<1],cur[maxn<<1];queue<int>qu;bool bfs(){memset(num,0,sizeof(num));num[ss]=1; qu.push(ss);while(qu.size()){int u=qu.front(); qu.pop();for(int i=beg[u];i;i=las[i]){if(!flow[i] || num[to[i]])continue;num[to[i]]=num[u]+1;qu.push(to[i]);}}return num[tt]!=0;}int dfs(int u,int res){if(u==tt || !res)return res;int ret=0,f;for(int &i=cur[u];i;i=las[i]){if(num[to[i]]!=num[u]+1)continue;if((f=dfs(to[i],min(res,flow[i])))){ret+=f;res-=f;flow[i]-=f;flow[i^1]+=f;}if(!res)break;}return ret;}void work(){while(bfs()){REP(i,ss,tt)cur[i]=beg[i];sumf+=dfs(ss,inf);}} }T;bool init(){scanf("%d",&n);double tmp;REP(i,1,n)REP(j,1,n){scanf("%lf",&tmp);a[i][j]=floor(tmp);b[i][j]=ceil(tmp);if(i==n && j==n && tmp)return false;}REP(i,1,n-1){c[i]+=a[i][n];REP(j,1,n-1)c[i]-=a[i][j];}REP(i,1,n-1){c[i+n-1]-=a[n][i];REP(j,1,n-1)c[i+n-1]+=a[j][i];}s=n*2-1; t=n*2;ss=0; tt=n*2+1;REP(i,1,n-1){add(s,i,b[i][n]-a[i][n]);add(i+n-1,t,b[n][i]-a[n][i]);}REP(i,1,n-1)REP(j,1,n-1)add(i,j+n-1,b[i][j]-a[i][j]);int sum1=0,sum2=0;REP(i,1,n-1){sum1+=a[i][n];sum2+=a[n][i];}add(s,tt,sum1);add(ss,t,sum2);sum+=sum2;REP(i,1,n-1){if(c[i]>0)sum+=c[i];if(c[i]>0)add(ss,i,c[i]);else add(i,tt,-c[i]);if(c[i+n-1]>0)add(ss,i+n-1,c[i+n-1]);else add(i+n-1,tt,-c[i+n-1]);}add(t,s,inf);return true; }int main(){File();if(init()){T.work();if(sum!=sumf){puts("No");return 0;}ans=flow[cnte];sumf=0;beg[ss]=0; beg[tt]=0;beg[t]=las[beg[t]]; beg[s]=las[beg[s]];REP(i,1,2*n)beg[i]=las[beg[i]];add(ss,s,inf); add(t,tt,inf);T.work();printf("%d\n",(ans+sumf)*3);}else puts("No");return 0; }

總結(jié)

以上是生活随笔為你收集整理的[bzoj3698]XWW的难题——有上下界的最大流的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。