首页 > 其他分享 >ABC347G 题题解

ABC347G 题题解

时间:2024-04-02 20:46:27浏览次数:20  
标签:int 题解 long ABC347G Add Dinic col dis

还算是比较经典了。

首先我们注意到一个性质:\(1 + 3 + \cdots + n = n ^ 2\)。所以我们可以把平方拆开。

然后容易证明 \(a_{i, j}\) 填 \(1\) 一定比填 \(0\) 不劣。

我们可以把 \(a_{i, j}\) 拆成 \(4\) 个点,然后我们想到了最小割。

构造网络:

  • \(a_{i, j, x} \leftarrow a_{i, j, x + 1}\),权重为 \(+\infty\)。

  • 若 \(a_{i, j} != 0\),\(\forall x \neq a_{i, j} - 1\),\(a_{i, j, x} \rightarrow a_{i, j, x + 1}\),权重为 \(+\infty\)。

  • 对于相邻的两个点 \(A, B\),\(\forall x > y, a_{A, x} \rightarrow a_{B, y}\), 权重为 \(2\)。

  • 对于相邻的两个点 \(A, B\),\(\forall x, a_{A, x} \rightarrow a_{B, x}\), 权重为 \(1\)。

容易证明这个网络的最小割即为所求。

按照 Dinic 跑最大流,残量网络即为最小割。时间复杂度 \(\mathcal{O}(F\times m) = \mathcal{O}(n^4 \times d^4)\),能过。

/*******************************
| Author:  DE_aemmprty
| Problem: G - Grid Coloring 2
| Contest: AtCoder - AtCoder Beginner Contest 347
| URL:     https://atcoder.jp/contests/abc347/tasks/abc347_g
| When:    2024-04-02 12:29:05
| 
| Memory:  1024 MB
| Time:    2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;

long long read() {
    char c = getchar();
    long long x = 0, p = 1;
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') p = -1, c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x * p;
}

const int N = 1607;

struct Edge {
    int v;
    long long w;
    int nxt;
} e[N * N];

int n, P;
int hd[N], tot;

void add(int u, int v, long long w) {
    e[++ tot] = {v, w, hd[u]};
    hd[u] = tot;
}

namespace Dinic {
    long long ans, dis[N], now[N];
    int grp[N];
    bool Build(int x, int t) {
        queue <int> q;
        fill(dis + 1, dis + P + 1, 2e18);
        q.push(x); dis[x] = 0, now[x] = hd[x];
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (u == t) return true;
            for (int i = hd[u]; i > 1; i = e[i].nxt) {
                int v = e[i].v, w = e[i].w;
                if (w != 0 && dis[v] == 2e18) {
                    dis[v] = dis[u] + 1;
                    now[v] = hd[v];
                    q.push(v);
                }
            }
        }
        return false;
    }
    long long update(int x, int t, long long sum) {
        if (x == t) return sum;
        long long res = 0;
        for (int i = now[x]; i > 1 && sum; i = e[i].nxt) {
            now[x] = i;
            long long v = e[i].v, w = e[i].w;
            if (w > 0 && dis[v] == dis[x] + 1) {
                long long p = update(v, t, min(sum, w));
                if (!p) dis[v] = 2e18;
                e[i].w -= p;
                e[i ^ 1].w += p;
                res += p;
                sum -= p;
            }
        }
        return res;
    }
    long long Dinic(int s, int t) {
        ans = 0;
        while (Build(s, t))
            ans += Dinic::update(s, t, 2e18);
        return ans;
    }
    void MinCut(int s, int t) {
        for (int i = 1; i <= P; i ++)
            if (dis[i] != 2e18)
                grp[i] = 1;
            else
                grp[i] = 0;
    }
    void Add(int u, int v, long long w) {
        add(u, v, w);
        add(v, u, 0);
    }
}

int a[27][27];
int col[27][27][17];

void solve() {
    n = read();
    for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
        a[i][j] = read();
    tot = 1; P = 2;
    for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) {
        // col[i][j][0] = 1, col[i][j][5] = 2;
        for (int x = 1; x <= 4; x ++) col[i][j][x] = ++ P;
    }
    for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
        for (int x = 2; x <= 4; x ++)
            Dinic::Add(col[i][j][x], col[i][j][x - 1], 2e18);
    for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
        if (a[i][j]) {
            if (a[i][j] > 1) Dinic::Add(1, col[i][j][a[i][j] - 1], 2e18);
            if (a[i][j] < 5) Dinic::Add(col[i][j][a[i][j]], 2, 2e18);
        }
    for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
        for (int x = 1; x <= 4; x ++) for (int y = 1; y <= x; y ++) {
            if (y < x) {
                if (i < n) Dinic::Add(col[i][j][x], col[i + 1][j][y], 2);
                if (i > 1) Dinic::Add(col[i][j][x], col[i - 1][j][y], 2);
                if (j < n) Dinic::Add(col[i][j][x], col[i][j + 1][y], 2);
                if (j > 1) Dinic::Add(col[i][j][x], col[i][j - 1][y], 2);
            } else {
                if (i < n) Dinic::Add(col[i][j][x], col[i + 1][j][x], 1);
                if (i > 1) Dinic::Add(col[i][j][x], col[i - 1][j][x], 1);
                if (j < n) Dinic::Add(col[i][j][x], col[i][j + 1][x], 1);
                if (j > 1) Dinic::Add(col[i][j][x], col[i][j - 1][x], 1);
            }
        }
    Dinic::Dinic(1, 2);
    Dinic::MinCut(1, 2);
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            int px = 1;
            for (int x = 1; x <= 4; x ++)
                px += Dinic::grp[col[i][j][x]];
            cout << px << ' ';
        }
        cout << '\n';
    }
}

signed main() {
    int t = 1;
    while (t --) solve();
    return 0;
}

标签:int,题解,long,ABC347G,Add,Dinic,col,dis
From: https://www.cnblogs.com/aemmprty/p/18111446

相关文章

  • 三道dp的题解报告
    三道dp的题解报告圆题目来源牛客练习赛122D题练习赛链接https://ac.nowcoder.com/acm/contest/75768题面原题面为中文就直接放原题面截图了。解法事实上,把\(n\)与\(1\)断掉,断环为链,把原来的线段看成区间,线段相交就是区间之间部分覆盖(区间有重复部分但是没有相互包含关......
  • 题解:AT_abc176_e [ABC176E] Bomber
    分析我们可以用\(hf\)和\(wf\)分别储存每行的目标数及每列的目标数。然后我们可以贪心:若想摧毁最多的目标,则选定的位置所在的行是所有行中目标最多的,所在的列是所有列中目标最多的(感性理解一下)。但是,选定的位置也可能有一个目标。在统计摧毁的目标数时,该目标被算了两次......
  • P2143 [JSOI2010] 巨额奖金 题解
    P2143[JSOI2010]巨额奖金题解矩阵树定理+Kruskal最小生成树计数。思路MST都是喵喵题。引理1:所有合法的权值相同边的连边方案,得到的连通块情况是相同的。感性理解:如果不相同意味着至少有一条边可以连通一对连通块。所以我们可以这么做:先跑Kruskal标记树边,然后枚举......
  • P1967 [NOIP2013 提高组] 货车运输 题解
    P1967[NOIP2013提高组]货车运输原题地址思路:由于题目要求的是使两点之间的最小边权最大,所以可以构造最大生成树(最大生成树一定是最大瓶颈生成树,而瓶颈生成树上两点之间的路径,在原图中的所有路径中,最小边权仍然最大,即满足题目要求,详见https://oi-wiki.org/graph/mst/#性质),......
  • Golang | Leetcode Golang题解之第4题寻找两个正序数组的中位数
    题目:题解:funcfindMedianSortedArrays(nums1[]int,nums2[]int)float64{iflen(nums1)>len(nums2){returnfindMedianSortedArrays(nums2,nums1)}m,n:=len(nums1),len(nums2)left,right:=0,mmedian1,median2:=0,0......
  • CF1935D Exam in MAC 题解
    ExaminMAC题意\(t\)组数据。给定一个大小为\(n\)的集合\(s\)和一个整数\(c\),保证\(0\leqslants_i\leqslantc(1\leqslanti\leqslantn)\)。求有多少对整数数对\((x,y)\),满足:\(0\leqslantx\leqslanty\leqslantc\)。\(x+y\notins\)且\(y-x\not......
  • 2024最新一线互联网大厂常见高并发面试题解析
    面试官:临界区是什么?答:临界区用来表示一种公共资源或者说是共享资源,可以被多个线程使用。但是每一次,只能有一个线程使用它,一旦临界区资源被占用,其他线程要想使用这个资源,就必须等待。比如,在一个办公室里有一台打印机,打印机一次只能执行一个任务。如果小王和小明同时需要打......
  • 【赛题解析】【移动应用开发】全国职业院校技能大赛任务一:实现社区首页功能解析
    ​培训、环境、资料、考证公众号:波比网络公众号2:波比网络工作室移动应用开发技能大赛交流群:548238632波比网络专注于技能提升,赋能**本文章全文由波比网络原创,非法转载必究!**文章目录移动应用与开发任务1:实现社区首页功能1.界面顶部显示所在社区名称、轮播图和社......
  • IDEA中新建SpringBoot模块,JDK版本问题解决
    问题描述IDEA中新建SpringBoot模块,使用的JAVAJDK1.8,新建模块时选项中没有JDK8: 运行时报错,JDK之类的问题解决方案,查看修改以下四个地方:(1)设置-Java编译器 (2)项目结构--依赖以及源码 ......
  • 哈尔滨理工大学3-31校赛模拟赛第一场题解
    概览:ABF为签到题,CE模拟,D深搜,G最短路,H双指针A.提取数字:注意前导零的情况需要排除,由于组成的数不超过longlong范围,所以直接用res承接就好了#include<iostream>usingnamespacestd;longlongres;intmain(){charc;while(cin>>c)if(c>='0'&&c<='9......