題目：Matrix

?

之所以能夠用最大流解決這個問題，關鍵在于最大流可以求解下面這個函數的最小值：

接下來就分析一下如何用最大流求解上面這個函數的極值。

首先xi一共只有兩種選擇，那么最終可以按xi的取值將xi劃分成兩個集合，那么如果xi在值為1的集合里，xj在值為0的集合里，那么就會

產生一個代價cij。同時如果xi選擇0就會產生一個bi的代價，如果xi選擇1就會產生一個ai的代價。于是構造一個源點S，匯點T做最小

割，不妨假設做完最小割之后值為1的xi的集合是和S相連的部分，值為0的xi的集合是和T相連的部分。

?

由于表達式中有三項，我們用三種割邊來分別描述這三項的值。一種是xi選擇了1，這樣就不能選擇0，需要把xi-T這條邊割掉，由于xi

選擇1會產生ai的代價，那么就把這條邊的容量設為ai。另一種是xi選擇了0，這樣就不能選擇1，需要把S-xi這條邊割掉，由于xi選擇0會

產生bi的代價，那么就把這條邊的容量設為bi。最后一種是xi選擇了1，xj選擇了0，這樣xi和xj不能在同一個集合中，需要把xi-xj這條邊割

掉，由于xi選擇1，xj選擇0產生cij的代價，那么就把這條邊的容量設為cij。這樣對建好的圖做最小割就可以得到上面哪個函數的最小

值。

?

接著我們分析這個題目如何轉化成上面這種模型。首先我們將D的表達式赤裸裸地寫出來：

這種形式必然不能看出來和上面那個表達式有什么關系，于是我們繼續將其化簡：

如果令f等于最后一行括號里的內容，那么發生了什么？如果ai選擇0會產生sum{bij}(1<=j<=N)的代價，如果ai選擇1會產生ci的代價，如

果ai選擇1且aj選擇0就會產生bij的代價。這樣就完全轉化成了上面的模型。

#include <iostream> #include <stdio.h> #include <string.h>using namespace std;const int N=2050; const int M=2500000; const int INF=0x7fffffff;int e; int ver[M],next[M],flow[M]; int head[N],work[N],dis[N],q[N];void init() {e=0;memset(head,-1,sizeof(head)); }void add(int u,int v,int c) {ver[e]=v;flow[e]=c;next[e]=head[u];head[u]=e++;ver[e]=u;flow[e]=0;next[e]=head[v];head[v]=e++; }int bfs(int S,int T) {int rear=0;memset(dis,-1,sizeof(dis));dis[S]=0;q[rear++]=S;for(int i=0;i<rear;i++){for(int j=head[q[i]];j!=-1;j=next[j]){if(flow[j]&&dis[ver[j]]==-1){dis[ver[j]]=dis[q[i]]+1;q[rear++]=ver[j];if(ver[j]==T) return 1;}}}return 0; }int dfs(int cur,int a,int T) {if(cur==T) return a;for(int &i=work[cur];i!=-1;i=next[i]){if(flow[i]&&dis[ver[i]]==dis[cur]+1){int t=dfs(ver[i],min(a,flow[i]),T);if(t){flow[i]-=t;flow[i^1]+=t;return t;}}}return 0; }long long Dinic(int S,int T) {long long ans=0;while(bfs(S,T)){memcpy(work,head,sizeof(head));while(int t=dfs(S,INF,T)) ans+=t;}return ans; }int main() {long long sum;int t,n,x,a,S,T;scanf("%d",&t);while(t--){scanf("%d",&n);init();S=0;T=n+1;sum=0;for(int i=1;i<=n;i++){a=0;for(int j=1;j<=n;j++){scanf("%d",&x);a+=x;add(i,j,x);}sum+=a;add(S,i,a);}for(int i=1;i<=n;i++){scanf("%d",&x);add(i,T,x);}printf("%I64d\n",sum-Dinic(S,T));}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU4307(最小割)的全部內容，希望文章能夠幫你解決所遇到的問題。

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