題意： $n\times n$ 的 01 矩陣，對于 $i\in [1,n]$ 有三個參數 $l_i,l_i,k_i$，表示第 $i$ 行，第 $i$ 列的 $1$ 的個數分別在 $[l_i,r_i]$ 中，且差的絕對值不超過 $k_i$。每個元素可以花費 $c_{i,j}$ 修改，也有不可修改的元素。求最少代價滿足限制。保證有解。

$n\le 100$

顯然是個最小費用可行流。

行列分別建點，對每個 $i$ 建一個虛點。行的點出度代表這一行的 $1$ 的個數，列的點入度代表這一列的 $1$ 的個數，通過虛點來達成限制。

具體而言，把這三個點連成一個環流，與虛點連接的邊限對應的上下界。對于差的絕對值，相當于該虛點允許 $k_i$ 范圍內的流量不平衡，新建超級源匯 $S,T$,$S$ 往虛點，虛點往 $T$ 連流量為 $k_i$ 的邊。

對于矩陣中的點，如果原來是 $0$ 就正常連邊，如果是 $1$ 就強制流 $1$ 建反向邊。

因為兩條 $k_i$ 的邊可以不滿流，所以不能直接跑。從 $T$ 往 $S$ 連無窮的流量，然后新建超超級源匯 $SS,ST$ 來達到可行流條件。

然后跑最小費用可行流即可，即 $SS$ 到 $ST$ 的最小費用最大流。

注意原來的 $S,T$ 就只是來調整平衡的，不要在上面做些奇怪的事情。

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <queue> #define MAXN 405 #define MAXM 2000005 using namespace std; const int INF=0x7fffffff; typedef long long ll; inline int read() {int ans=0,f=1;char c=getchar();while (!isdigit(c)) (c=='-')&&(f=-1),c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return f*ans; } struct edge{int u,v,c,w;}e[MAXM]; int head[MAXN],cur[MAXN],nxt[MAXM],cnt=1; inline void insert(int u,int v,int c,int w) {e[++cnt]=(edge){u,v,c,w};nxt[cnt]=head[u];head[u]=cnt; } inline void addnode(int u,int v,int c,int w){insert(u,v,c,w),insert(v,u,0,-w);} int dis[MAXN],vis[MAXN],S,T; bool spfa() {memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[S]=0,vis[S]=1;queue<int> q;q.push(S);while (!q.empty()){int u=q.front();q.pop();vis[u]=0;for (int i=head[u];i;i=nxt[i])if (e[i].c&&dis[u]+e[i].w<dis[e[i].v]){dis[e[i].v]=dis[u]+e[i].w;if (!vis[e[i].v]) q.push(e[i].v),vis[e[i].v]=1;}}return dis[T]<dis[0]; } ll cost; int dfs(int u,int f) {if (u==T||!f) return f;int used=0;vis[u]=1;for (int& i=cur[u];i;i=nxt[i])if (e[i].c&&!vis[e[i].v]&&dis[u]+e[i].w==dis[e[i].v]){int w=dfs(e[i].v,min(f,e[i].c));if (!w) continue;e[i^1].c+=w,e[i].c-=w;used+=w,f-=w;cost+=(ll)w*e[i].w;if (!f) break;}return used; } inline int dinic() {int mflow=0;while (spfa()){memcpy(cur,head,sizeof(cur));mflow+=dfs(S,INF);}return mflow; } int A[MAXN][MAXN],C[MAXN][MAXN],s[MAXN]; int main() {int n=read();for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)A[i][j]=read();for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)C[i][j]=read();int SS=3*n+1,ST=3*n+2;for (int i=1;i<=n;i++){int l,r,k;l=read(),r=read(),k=read();s[i]+=l,s[i+2*n]-=l,addnode(i+2*n,i,r-l,0);s[i+2*n]+=l,s[i+n]-=l,addnode(i+n,i+2*n,r-l,0);addnode(SS,i+2*n,k,0),addnode(i+2*n,ST,k,0);}addnode(ST,SS,INF,0);int cur=cnt+1;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){if (A[i][j]) ++s[j+n],--s[i];if (~C[i][j]){if (A[i][j]) addnode(j+n,i,1,C[i][j]);else addnode(i,j+n,1,C[i][j]);}}S=3*n+3,T=3*n+4;int sum=0;for (int i=1;i<=3*n;i++){if (s[i]>0) sum+=s[i],addnode(S,i,s[i],0);else if (s[i]<0) addnode(i,T,-s[i],0);}cerr<<dinic()<<' '<<sum<<'\n';cout<<cost<<'\n';for (int i=1;i<=n;i++,puts(""))for (int j=1;j<=n;j++){if (~C[i][j]){if (!e[cur].c) A[i][j]^=1;cur+=2;}printf("%d ",A[i][j]);}return 0; }

總結

以上是生活随笔為你收集整理的【UOJ575】光伏元件【网络流建图】【上下界网络流】【费用流】的全部內容，希望文章能夠幫你解決所遇到的問題。

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