思路：
把每個方塊拆成兩個點
1個入點 1個出點
當前格子的入->出連費用-w[i][j] 容量1的邊
當前格子的入->出連費用0 容量k-1的邊
此格子的出向右&下（如果有的話）的格子的入連費用0容量k的邊

//By SiriusRen #include <queue> #include <cstdio> #include <cstring> using namespace std; #define N 55 #define maxn 5555 #define M 20050 #define mem(x,y) memset(x,y,sizeof(x)) int n,k,In[N][N],Out[N][N],cnt,a[N][N],vis[maxn],d[maxn],minn[maxn],with[maxn]; int first[maxn],next[M],v[M],edge[M],cost[M],tot,ans; void Add(int x,int y,int C,int E){edge[tot]=E,cost[tot]=C,v[tot]=y,next[tot]=first[x],first[x]=tot++;} void add(int x,int y,int C,int E){Add(x,y,C,E),Add(y,x,-C,0);} bool tell(){mem(vis,0),mem(d,0x3f),mem(minn,0x3f),mem(with,0);queue<int>q;q.push(0),d[0]=0;while(!q.empty()){int t=q.front();q.pop();vis[t]=0;for(int i=first[t];~i;i=next[i])if(d[v[i]]>d[t]+cost[i]&&edge[i]){d[v[i]]=d[t]+cost[i],minn[v[i]]=min(minn[t],edge[i]),with[v[i]]=i;if(!vis[v[i]])vis[v[i]]=1,q.push(v[i]);}}return d[cnt]!=0x3f3f3f3f; } int zeng(){for(int i=cnt;i;i=v[with[i]^1])edge[with[i]]-=minn[cnt],edge[with[i]^1]+=minn[cnt];return d[cnt]; } int main(){memset(first,-1,sizeof(first));scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]),In[i][j]=++cnt,Out[i][j]=++cnt;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){add(In[i][j],Out[i][j],-a[i][j],1);add(In[i][j],Out[i][j],0,k-1);if(In[i+1][j])add(Out[i][j],In[i+1][j],0,k);if(In[i][j+1])add(Out[i][j],In[i][j+1],0,k);}add(0,1,0,k),add(cnt,cnt+1,0,k),cnt++;while(tell())ans+=zeng();printf("%d\n",-ans); }

轉載于:https://www.cnblogs.com/SiriusRen/p/6532116.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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