Luogu_2774 方格取數問題

二分圖最小割

第一次做這種題，對于某些強烈暗示性的條件并沒有理解到。

也就是每一立刻理解到是這個圖是二分圖。

為什么？
橫縱坐標為奇數的只會和橫縱坐標為偶數的相連。

最大和=全局和-最小代價

所以可以反向縮小最小代價。

考慮奇數點與源點相連，偶數點與匯點相連，流量都是這個點的權值。

然后奇數點像偶數點連邊，權值無限大。

這樣構圖。最小割是一個簡單割。

割的流量就是最小的代價。

要么奇數點被割去，要么相鄰的四個偶數點被割去

#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <queue>using std::queue; using std::min;const int maxn=301; const int inf=0x7fffffff; const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0};struct node {int p;int nxt;int value;node(int a=0,int b=0,int c=0){p=a;value=b;nxt=c;} };node line[maxn*maxn<<1]; int head[maxn*maxn],tail; int cur[maxn*maxn]; int Dis[maxn*maxn]; int Map[maxn][maxn]; int S,T;void add(int a,int b,int c,int d) {line[++tail]=node(b,c,head[a]);head[a]=tail;line[++tail]=node(a,d,head[b]);head[b]=tail; }void init(int n,int m) {S=n*m;T=n*m+1;tail=-1;memset(head,-1,sizeof(head)); }int Bfs(int s,int t) {queue<int>q;memset(Dis,0,sizeof(Dis));Dis[s]=1;q.push(s);while(!q.empty()){int pas=q.front();q.pop();for(int i=head[pas];i!=-1;i=line[i].nxt){int v=line[i].p;if(Dis[v]||!line[i].value) continue;Dis[v]=Dis[pas]+1;q.push(v);}}for(int i=0;i<=T;i++) cur[i]=head[i];return Dis[t]; }int Dfs(int now,int aim,int limte) {if(now==aim||!limte) return limte;int res=0,f;for(int &i=cur[now];i!=-1;i=line[i].nxt){int v=line[i].p;if(Dis[v]==Dis[now]+1&&(f=Dfs(v,aim,min(limte,line[i].value)))){res+=f;limte-=f;line[i].value-=f;line[i^1].value+=f;if(!limte) break;}}return res; }int Dinic(int s,int t) {int res=0;while(Bfs(s,t))res+=Dfs(s,t,inf);return res; }int main() {int n,m,tot=0;scanf("%d%d",&n,&m);init(n,m);for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&Map[i][j]);for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(((i+j)&1)==1){add(S,i*m+j,Map[i][j],0);for(int k=0;k<4;k++)if(i+dx[k]>=0&&i+dx[k]<n&&j+dy[k]>=0&&j+dy[k]<m)add(i*m+j,(i+dx[k])*m+(j+dy[k]),inf,0);}elseadd(i*m+j,T,Map[i][j],0);tot+=Map[i][j];}printf("%d",tot-Dinic(S,T));return 0; }

轉載于:https://www.cnblogs.com/Lance1ot/p/10295246.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Luogu_2774 方格取数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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