Codeforces 1416F. Showing Off 题解

题目链接：F. Showing Off

题目大意：洛谷

题解：如果将格子之间按方向连边，因为不允许走出边界，所以最后一定是若干个内向基环树。

容易发现环上的点的权值和一定一样大。

因为环的大小无所谓，本题中又显然不存在环长为奇数环，所以我们选定所有环长为 2 肯定不劣。

接下来考虑非环边，一个点能够存在非环边自然周围四格有至少一个格子的权值比它小，所以这些点可以不必处在环上，但是如果一个点周围四格都不比它小，那么这个点要强制选择。

如果没有强制选择的限制那么这一道题就变成了骨牌覆盖问题直接黑白染色建二分图跑网络流就可以了。

有了强制选择我们可以令这些边的边权变为 1 ，然后对于整张图跑最大费用最大流就结束了。

如果跑出来的代价不对直接输出无解就好了。

其实费用流应该改成有上下界的网络流才对，但是这题费用流跑得飞快我也就没管了。

时间复杂度不会证。

代码：

#include 
#include 
void read(int &a){
    a=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        a=(a<<1)+(a<<3)+(c^48);
        c=getchar();
    }
}
template
Elem_1 min(Elem_1 a,Elem_2 b){
    return an||ny>m){
                    continue;
                }
                if(a[nx][ny]n||ny>m){
                    continue;
                }
                if(a[nx][ny]==a[i][j]){
                    add_edge(id[i][j],id[nx][ny],1,0);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if((i+j)&1){
                add_edge(id[i][j],T,1,-(int)in[i][j]);
            }
            else{
                add_edge(S,id[i][j],1,-(int)in[i][j]);
            }
        }
    }
    int ans_2;
    Dinic(ans_2);
    ans_2=-ans_2;
    if(ans_2n||ny>m||a[nx][ny]>=a[i][j]){
                        continue;
                    }
                    s[i][j]=D[k];
                    w[i][j]=a[i][j]-a[nx][ny];
                    break;
                }
            }
        }
    }
    puts("YES");
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%d ",w[i][j]);
        }
        puts("");
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            putchar(s[i][j]);
            putchar(' ');
        }
        puts("");
    }
}
int main(){
    int T;
    read(T);
    while(T--){
        solve();
    }
    return 0;
}