Emmmm昨天晚上下第二节课回家, 本来觉得自己应该能在1h之内写完调完, 但是网络流板子好像出锅了? 好像加完当前弧优化就WA掉了? 去掉之后就可以过? 非常不能理解.
好吧我们来分析题目.
我们还是按照题目的要求来建图: - 不能选有公共边的格子, 我们可以很显然地想到黑白染色, 然后黑点一排, 白点一排. - 将源点与每个黑点相连(当然你想连白点也没人管), 流量是这个点的权值. - 将每个白点(如果之前连了白点那这次就连黑点咯), 流量是这个点的权值. - 将每个黑(白)点与和其有公共边的白(黑)点相连, 流量为 ∞ . - 那么割掉一个点与源点或汇点的连边就表示不选这个点. - 所以我们用所有点权的总和减去最小割就ok咯~
还是画一下样例建图(似乎windows下的画图还是要好用些←_←
然后就是代码
#include <queue> #include <cstdio> #include <cstring> using std::queue; const int N=1e4+8; const int M=1e5+5; const int INF=0x7f7f7f7f; inline int gn(int a=0,char c=0){ for(;c<'0'||c>'9';c=getchar()); for(;c>47&&c<58;c=getchar())a=a*10+c-48;return a; } struct edge{ int to,next,flow; }e[M]; int v[N],tot=1; void buildedge(int x,int y,int z){ e[++tot].to=y; e[tot].next=v[x]; e[tot].flow=z; v[x]=tot; e[++tot].to=x; e[tot].next=v[y]; e[tot].flow=0; v[y]=tot; } int d[N],cur[N],n,m,s,t,sum; queue<int> q; bool bfs(){ memset(d,-1,sizeof(d)); d[s]=0; q.push(s); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=v[x];i;i=e[i].next) if(e[i].flow&&d[e[i].to]<0){ d[e[i].to]=d[x]+1; q.push(e[i].to); } } return d[t]>0; } int dfs(int x,int mx,int s=0){ int k; if(!mx||x==t) return mx; for(int i=v[x];i;i=e[i].next){ if(d[e[i].to]==d[x]+1){ k=dfs(e[i].to,std::min(mx,e[i].flow)); if(k) s+=k,mx-=k,e[i].flow-=k,e[i^1].flow+=k; if(!mx) break; } } return s; } int main(){ n=gn(); m=gn(); s=0; t=n*m+1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ int k=(i-1)*m+j,x=gn(); sum+=x; if((i+j)&1){ buildedge(s,k,x); if(i>1) buildedge(k,k-m,INF); if(i<n) buildedge(k,k+m,INF); if(j>1) buildedge(k,k-1,INF); if(j<m) buildedge(k,k+1,INF); } else buildedge(k,t,x); } while(bfs()) sum-=dfs(s,INF); printf("%d",sum); }反正就这样吧 dinic板子是真的打不对了… 所以到底为什么当前弧优化会被卡啊QAQ
