思路

簡(jiǎn)單的拆點(diǎn)
拆成入點(diǎn)和出點(diǎn)，對(duì)應(yīng)點(diǎn)之間連一條cap=1，cost=x和一條cap=INF，cost=0的邊，然后相鄰點(diǎn)的出點(diǎn)和其他點(diǎn)的入點(diǎn)連邊，然后S有k的流量，然后跑最大費(fèi)用最大流就好了

代碼

#include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> using namespace std; struct Edge{int u,v,cap,cost,flow; }; const int MAXN = 10000; const int INF = 0x3f3f3f3f; vector<Edge> edges; vector<int> G[MAXN]; void addedge(int u,int v,int cap,int cost){edges.push_back((Edge){u,v,cap,cost,0});edges.push_back((Edge){v,u,0,-cost,0});int cnt=edges.size();G[u].push_back(cnt-2);G[v].push_back(cnt-1); } int d[MAXN],a[MAXN],p[MAXN],vis[MAXN],s,t; queue<int> q; bool spfa(int &flow,int &cost){memset(d,0x3f,sizeof(d));memset(p,0,sizeof(p));q.push(s);vis[s]=true;a[s]=INF;d[s]=0;while(!q.empty()){int x=q.front();q.pop();vis[x]=false;for(int i=0;i<G[x].size();i++){Edge &e = edges[G[x][i]];if(e.cap>e.flow&&d[x]+e.cost<d[e.v]){d[e.v]=d[x]+e.cost;a[e.v]=min(a[x],e.cap-e.flow);p[e.v]=G[x][i];if(!vis[e.v]){vis[e.v]=true;q.push(e.v);}}}}if(d[t]==INF)return false;flow+=a[t];cost+=d[t]*a[t];for(int i=t;i!=s;i=edges[p[i]].u){edges[p[i]].flow+=a[t];edges[p[i]^1].flow-=a[t];}return true; } void MCMF(int &flow,int &cost){flow=0,cost=0;while(spfa(flow,cost)); } int n,k; inline int id(int x,int y){return (x-1)*n+y; } int main(){scanf("%d %d",&n,&k);s=MAXN-2;t=MAXN-3;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){int x;scanf("%d",&x);addedge(id(i,j),id(i,j)+n*n,1,-x);addedge(id(i,j),id(i,j)+n*n,k-1,0); }for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i<n)//xiaaddedge(id(i,j)+n*n,id(i+1,j),INF,0);if(j<n)addedge(id(i,j)+n*n,id(i,j+1),INF,0);}addedge(s,id(1,1),k,0);addedge(id(n,n)+n*n,t,INF,0);int cost,flow;MCMF(flow,cost);printf("%d\n",-cost);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/dreagonm/p/10498439.html

總結(jié)

以上是生活随笔為你收集整理的P2045 方格取数加强版的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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