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