思维

UVALive 7505 Hungry Game of Ants

Posted on

老实说,这题我在现场赛大概写不出来。

感觉还是比较需要脑洞。

题意:
一排不同重量的蚂蚁按重量排成一排玩饥饿游戏,每只蚂蚁最开始选择一个方向,左或者右,大蚂蚁吃小蚂蚁,并且使自己增加小蚂蚁的重量,如果重量相同,左吃右。
问 n 只蚂蚁,第 k 只活到最后的方案数。

思路:

直接切入正解。
首先第k只蚂蚁必须选择左边,不然只能被吃。( $n \neq k $ )
如果想要第 k 只蚂蚁获胜,必须满足以下两个条件

  1. $ weight[ max(p_1), k ] > weight[ 0, max(p_1) ) $
  2. $ weight[ 1, min(p_2) ] <= weight( min(p_2), n ] $

其中,$ max(p_1) $ 是指,满足第一条不等式的最大的 $p_1$
同理,$ max(p_2) $ 是指,满足第二条不等式的最小的 $p_2$

而其中,只要满足第一条不等式,则 $ [1, max(p_1)) $ 的方向任意,所以数量为 $ 2^{max(p_1)-1} $ 。同时这也是 k 只蚂蚁 k 胜出 的方案数。

下面有一个关键地方,就是如何通过 k 只蚂蚁 k 胜出来推出 n 只蚂蚁 k 胜出。
让第 n-1 选择左边,方案数减少一半,但是第 n 只选择任意,方案数增加一倍。故方案数不变。
以此类推。得 $ dp[n] = \sum_{i=w}^{n-1} dp[i]$ 其中 $(w = min(sum[w] \geq sum[n] - sum[w] ) ) $
这个地方只要求一下后缀和就好了。

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 5;

ll sum[maxn], dp[maxn], texp[maxn], tot[maxn];
int bit[maxn];

void init()
{
    texp[0] = 1;
    for (int i = 1; i < maxn; i++) {
        sum[i] = sum[i - 1] + i;
        texp[i] = texp[i - 1] * 2 % mod;
        bit[i] = lower_bound(sum, sum + i + 1, (sum[i] + 1) / 2) - sum;
    }
}

int main()
{
    int n, k, T;
    init();
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d", &n, &k);
        if (n == 1 && k == 1) {
            puts("2");
            continue;
        }
        ll s = k;
        memset(dp, 0, sizeof(dp));
        for (int i = k - 1; i >= 1; i--) {
            if (s > sum[i]) {
                tot[k] = dp[k] = texp[i + 1];
                break;
            }
            s += i;
        }
        for (int i = k + 1; i <= n; i++) {
            int tmp = bit[i];
            if (tmp - 1 >= k)
                dp[i] = ((tot[i - 1] - tot[tmp - 1]) % mod + mod) % mod;
            else
                dp[i] = tot[i - 1];
            tot[i] = (tot[i - 1] + dp[i]) % mod;
        }
        printf("Case #%d: %lld\n", cas, dp[n]);
    }
    return 0;
}
最小割

51Nod 1499 图

Posted on

emmmmmmm不错的的最小割吧
唯一一个不是很好的点就是实在是太容易想到是最小割了,但是没想到具体的建图方法。

题意:
有n个点,m条边,要你分成两个集合,使得两个集合的导出子图各自权值和的和最大。
两个导出子图中,可选择其中一个,若导出子图中存在有两个点 (i,j) 相连,则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反,只有存在两个点没有边相连,才会增加权值。

思路:
题目的主要目的就是将点集分成两部分,这很容易想到二分图染色,但这是不现实的,因为这是一个最值问题,不存在必然关系。
而跟二分图相关的只有网络流了,将图分为两半是割的概念,当然只存在最小割,正面去想的话,就是总权值和-最小割。

然后……思路就断了,找不到有效的建图方法。

可以先这么想,我们假定与源点相连的点集为相连增加权值的集合,并称之为,与汇点相连的点集则相反,称之为汇点集。
那么我们先将每个点都与源点相连,其容量为将该点加入源点集所能增加的权值。
再将这个点与汇点相连,其容量为将该点加入汇点集所能增加的权值。

此时直接跑最小割是不对的,因为这些点并不是独立的。

其实只要再将任意两个点都连边就可以了。

啊,顺便发现一个,换一种无向图建边,速度快了一倍,因为边几乎少了一半

AC Code

#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e3 + 5;
const int maxm = 5e6 + 5;
const int inf = 0x3f3f3f3f;

int src, des, idx;
int cur[maxn], level[maxn], head[maxn];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];

queue<int> que;

void addEdge(int u, int v, int c, int rc = 0)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], rc);//无向边建边小技巧
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(src);
    level[src] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[des] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == des)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic(int n)
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= n + 1; i++)
            cur[i] = head[i];
        while ((cflow = dfs(src, inf)))
            ans += cflow;
    }
    return ans;
}

void init(int s, int d)
{
    memset(head, -1, sizeof head);
    idx = 0;
    src = s, des = d;
}

bool g[maxn][maxn];
int s[maxn], t[maxn];

inline void scan_d(int& num)
{
    char in;
    in = getchar();
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
}

int main()
{
    int n, m, u, v, tmp;
    scan_d(n), scan_d(m);
    init(0, n + 1);
    while (m--) {
        scan_d(u), scan_d(v);
        g[u][v] = g[v][u] = true;
    }
    range(i, 1, n) range(j, i + 1, n)
    {
        tmp = j - i;
        if (g[i][j])
            s[i] += tmp, s[j] += tmp;
        else
            t[i] += tmp, t[j] += tmp;
        addEdge(i, j, tmp, tmp);
    }
    int ans = 0;
    range(i, 1, n) addEdge(src, i, s[i]), addEdge(i, des, t[i]);
    range(i, 1, n) ans += (1 + n - i) * (n - i) / 2;
    printf("%d\n", ans - dinic(n) / 2); //因为与源点汇点相连的点增加了一倍权值
    return 0;
}
强联通分量

CodeForces 864F Cities Excursions

Posted on

对Tarjan的算法理解有点要求的题,之前看了一下思路,敲了一下结果没过,照着博客改动了一下但并没有搞懂,今天补上。

题意:
给你一个有向图,若干询问,询问为从 s 到 t 的最小字典序路径中,第 k 个点是哪个点。

思路:
首先询问很多,有$4\times10^5$个询问,直接一个一个找肯定是不行的。
但是值得注意的是,点数比较少,只有$3000$个,假如我们固定起点,遍历全图来获得路径,在遍历的同时,对每一个点来记录答案。理想复杂度为$O(N^2)$,时间上满足条件。

一个问题是如何保证字典序最小,emmmm
用vector记录整张图,对于每个点的边进行排序,因为每个点访问一次,解决之。

这题还有一个合理的大坑,如果在遍历的时候,在之前已经出现了一个环,那么之后的所有点就都不会被访问。
当然你不能在找到一个环后,后面的点就不再遍历,这样会使最小字典树发生变化,会导致错误答案。
好题啊。

以上。

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 3e3 + 5;
const int maxq = 4e5 + 5;

struct Item {
    int u, v, q, id;
    bool operator<(const Item& item) const { return u < item.u; }
} items[maxq];

int dfn[maxn], low[maxn], vis[maxn], vtm;
int path[maxn], ans[maxq];
vector<int> G[maxn];
vector<Item> qary[maxn];

void tarjan(int u, int dep, bool cant)
{
    path[dep] = u;
    low[u] = dfn[u] = ++vtm;
    vis[u] = 1;
    int sz = qary[u].size();
    if (!cant)
        each(i, sz)
        {
            Item& item = qary[u][i];
            if (item.q <= dep)
                ans[item.id] = path[item.q];
        }
    sz = G[u].size();
    each(i, sz)
    {
        int v = G[u][i];
        if (!vis[v]) {
            tarjan(v, dep + 1, cant | (low[u] < dfn[u]));
            low[u] = min(low[u], low[v]);
            cant |= (low[v] < dfn[v]);
        } else if (vis[v] == 1)
            low[u] = min(low[u], dfn[v]);
    }
    vis[u] = 2;
}

int main()
{
    int n, m, q, u, v;
    scanf("%d %d %d", &n, &m, &q);
    each(i, m)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
    }
    range(i, 1, n) sort(G[i].begin(), G[i].end());
    each(i, q)
    {
        Item& item = items[i];
        scanf("%d %d %d", &item.u, &item.v, &item.q);
        item.id = i;
    }
    sort(items, items + q);
    fill(ans, -1);
    each(i, q)
    {
        Item& item = items[i];
        qary[item.v].push_back(item);
        if (i == q - 1 || item.u != items[i + 1].u) {
            vtm = 0, fill(vis, 0);
            tarjan(item.u, 1, false);
            range(j, 1, n) qary[j].clear();
        }
    }
    each(i, q) printf("%d\n", ans[i]);
    return 0;
}
区间DP

POJ 1991 Turning in Homework

Posted on

/doge薛昊老是偷我题做,最近我也就拿他博客上的题来练练手。其中这道题真的什么思路都没有,这个区间DP的套路我还真没碰到过。

这是一个大区间推小区间的套路。

题意:
小明要在某层楼的各个老师那里交一大堆作业,但是小明来早了,老师还没上班,他站在这层楼的最左边,告诉你每个老师的上班时间,最后要在某个给定位置下楼,问最少时间。

思路:
shit,完全是看博客,看代码敲的。
一个比较困难的点在于给定离开地点,算了,不装了,就算取消这个条件我也写不来……
明确可以用dp求解,首先按照位置优先开门顺序次优的顺序排序,设三维数组 $dp[l][r][k]$。
当 $k=0$ 时,表示只有 $(l,r] $ 区间内的作业没有交。
而 $k=1$ 时,表示只有 $[l,r) $ 区间内的作业没有交。
而我们的其实状态$dp[1][n][0/1]$是已知的,我们完全可以由此不断向内挤压求出小区间的结果。
当 $l=r$ 时,则所有作业交完,且停在 $l$ 点。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
int dp[maxn][maxn][2];
pii point[maxn];

int getDis(int d, int s) { return point[d].first - point[s].first; }

int main()
{
    int n, h, b;
    scanf("%d %d %d", &n, &h, &b);
    range(i, 1, n) scanf("%d %d", &point[i].first, &point[i].second);
    sort(point + 1, point + 1 + n);
    fill(dp, 0x3f);
    dp[1][n][0] = max(point[1].first, point[1].second);
    dp[1][n][1] = max(point[n].first, point[n].second);
    rrange(len, 1, n - 1) range(l, 1, n + 1 - len)
    {
        int r = l + len - 1;
        if (l > 1) {
            dp[l][r][0] = min(dp[l][r][0], dp[l - 1][r][0] + getDis(l, l - 1));
            dp[l][r][1] = min(dp[l][r][1], dp[l - 1][r][0] + getDis(r, l - 1));
        }
        if (r < n) {
            dp[l][r][0] = min(dp[l][r][0], dp[l][r + 1][1] + getDis(r + 1, l));
            dp[l][r][1] = min(dp[l][r][1], dp[l][r + 1][1] + getDis(r + 1, r));
        }
        dp[l][r][0] = max(dp[l][r][0], point[l].second);
        dp[l][r][1] = max(dp[l][r][1], point[r].second);
    }
    int ans = inf;
    range(i,1,n) ans = min(ans,dp[i][i][0]+abs(b-point[i].first));
    printf("%d\n",ans);
    return 0;
}
最小割

HihoCoder 1252 Kejin Game

Posted on

网络流建图神题!!!
同时也是2015年北京现场赛的金牌题,虽然我不可能去挑战金牌,但是也只有做这种神题,尽管不是自己想得,但A了之后仍然充满了满足。

题意:
给你一个DAG,表示一个游戏的技能树,也就是说某一些技能存在前置技能,但实际上这是为氪金大佬准备的游戏,有钱是真的可以为所欲为的,大佬们可以选择花钱直接无视所有前置技能直接习得某一个技能,也可以消除掉两个技能之间的依赖关系。

现在某个节俭的大佬想要学某一个技能,问最小花费。

思路:
说实话这道题一眼真的很容易想到图上DP,但是存在可以消除一个依赖的权利,使得DP存在后效性。
正解是最小割建模,这个最小割建模真的是非常巧妙:

  1. 拆点建图,u -> u' 的容量是直接氪金习得这一技能的花费
  2. 如果u,v存在依赖关系 u -> v ,建边 u' -> v ,容量为消除这个依赖的费用
  3. 将源点与每一个技能连边,容量为按技能树学习的费用。
  4. 将所要求的技能与汇点相连,容量为 inf

最后跑一遍最大流就是答案。

网上很多题解到这里就没了,也没有一个像样点的解释。

对于学习技能来说,其实就是一个消除依赖的过程,当然你不氪金的话还要花费学习这个技能份额费用,直接将按技能树学习的费用也作为一个依赖,就无需考虑这个,这就是第三条建边规则。
按这么想的话,第一条和第二条也很好理解。
而当我所要学得那个技能的依赖全部消除的时候,那么源点与汇点也就会被分离,也就是被个开了,因为汇点只会与所要求的技能相连。

感觉还是有点说不好啊,如果还不懂的话,只要在纸上画一画,就会变得很显然了。

AC Code

#include 

using namespace std;

const int maxn = 2e3 + 5;
const int maxm = 2e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m, src, des, idx;
int cur[maxn], level[maxn], head[maxn];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm  que;

void addEdge(int u, int v, int c)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], 0); //无向图为 c 有向图为 0
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(src);
    level[src] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap &gt; 0 &amp;&amp; level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[des] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == des)
        return low;
    for (int&amp; id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap &gt; 0 &amp;&amp; level[v] == level[u] + 1
            &amp;&amp; (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}


int dinic() { int ans = 0, cflow; while (bfs()) { for (int i = 0; i <= 2 * n + 2; i++) cur[i] = head[i]; while ((cflow = dfs(src, inf))) ans += cflow; } return ans; } void init(int s, int d) { memset(head, -1, sizeof head); idx = 0; src = s, des = d; } inline int in(int x) { return x << 1; } inline int out(int x) { return x << 1 | 1; } int main() { int T, u, v, w, t; scanf("%d", &T); while (T--) { scanf("%d %d %d", &n, &m, &t); init(0, 1); while (m--) { scanf("%d %d %d", &u, &v, &w); addEdge(out(u), in(v), w); } for (int i = 1; i <= n; i++) { scanf("%d", &w); addEdge(src, in(i), w); } for (int i = 1; i <= n; i++) { scanf("%d", &w); addEdge(in(i), out(i), w); } addEdge(out(t), des, inf); printf("%d\n", dinic()); } return 0; }

…………不知道为什么不把代码分开就显示不出来……

最大团

HDU 5556 Land of Farms 附最大团最终模板

Posted on

一眼以为是状压DP……
但是仔细读题的话,会有一个致命条件是状压无法解决的。

偷看了一下薛昊的博客,回去路上还跟我说二分图不可能建出来,结果到头来却用HK写这题。

题意:
给你一张图,是矩阵的形式,在满足条件的情况下你要选择尽可能多的格子。

其条件如下

  • 如果选中一个格子,这个格子是数字,则相同数字的格子立刻被选中。
  • 每个被选中的格子不允许其四个相邻的格子中 存在被选中且与其不同的格子

思路:
实际上这道题的确很想状压,如果把题目中的第一个条件改成,与其选中格子联通且数字相同的格子立马被选中的话,状压可解。但事实并非如此。

其实可以把所有是数字且相同的格子作为一个点,每个 . 也作为一个点,再将其与四周连边,按题意来的话,略加思考,其实就是个最大独立集的裸题。
但是关键还是需要转化出来啊……

坑点,答案最小为 1 。

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 12;
const int maxv = maxn * maxn;

char mat[maxn][maxn];
int row, col;
int im[maxn][maxn];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
bool g[maxv][maxv];
int ans;

inline bool judgeIn(int x, int y) { return x >= 0 && x < row && y >= 0 && y < col; }

void init()
{
    memset(im, 0, sizeof im);
    memset(g, true, sizeof g);
    ans = 1;
}

int createGraph()
{
    int cnt = 0;
    map<char, int> mp;
    each(i, row) each(j, col) if (im[i][j] == 0)
    {
        if (mat[i][j] == '.')
            im[i][j] = ++cnt;
        else {
            if (mp.find(mat[i][j]) == mp.end())
                mp[mat[i][j]] = ++cnt;
            im[i][j] = mp[mat[i][j]];
        }
        g[cnt][cnt] = false;
    }
    each(x, row) each(y, col)
    {
        int u = im[x][y], v;
        each(i, 4)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (judgeIn(xx, yy) && u != (v = im[xx][yy]))
                g[u][v] = g[v][u] = false;
        }
    }
    return cnt;
}

int vex[maxv], dp[maxv];
int stk[maxv][maxv];

void dfs(int n, int sz, int dep)
{
    if (sz == 0) {
        ans = max(ans, dep);
        return;
    }
    each(i, sz)
    {
        int u = stk[dep][i];
        if (dep + dp[u] <= ans || dep + sz - i <= ans)
            return;
        vex[dep] = u;
        int cnt = 0;
        range(j, i + 1, sz - 1)
        {
            int v = stk[dep][j];
            if (g[u][v])
                stk[dep + 1][cnt++] = v;
        }
        dfs(n, cnt, dep + 1);
    }
}

int maxClique(int n)
{
    memset(dp, 0, sizeof dp);
    dp[n] = 1;
    rrange(i, 1, n - 1)
    {
        int sz = 0;
        range(j, i + 1, n) if (g[i][j]) stk[1][sz++] = j;
        vex[0] = i;
        dfs(n, sz, 1);
        dp[i] = ans;
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d %d", &row, &col);
        each(i, row) scanf("%s", mat[i]);
        init();
        int n = createGraph();
        printf("Case #%d: %d\n", cas, maxClique(n));
    }
    return 0;
}

模板:
这是最大团的模板,极大团计数的点 这个
因为觉得极大团计数并没有找到最优的写法,至少还有一个优化没学就先不放了。

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxv = 110;

struct MC {
    bool g[maxv][maxv];
    int stk[maxv][maxv], dp[maxv];
    int vex[maxv], mcv[maxv];
    int n, mc;

    void init(int _n)
    {
        n = _n;
        memset(dp, 0, sizeof dp);
        //建图
    }

    void dfs(int sz, int dep)
    {
        if (sz == 0) {
            if (dep > mc) {
                mc = dep;
                each(i, mc) mcv[i] = vex[i];
            }
            return;
        }
        each(i, sz)
        {
            int u = stk[dep][i];
            if (dep + dp[u] <= mc || dep + sz - i <= mc)
                return;
            vex[dep] = u;
            int cnt = 0;
            range(j, i + 1, sz - 1)
            {
                int v = stk[dep][j];
                if (g[u][v])
                    stk[dep + 1][cnt++] = v;
            }
            dfs(cnt, dep + 1);
        }
    }

    int maxClique()
    {
        dp[n] = 1;
        rrange(i, 1, n - 1)
        {
            int sz = 0;
            range(j, i + 1, n) if (g[i][j]) stk[1][sz++] = j;
            vex[0] = i;
            dfs(sz, 1);
            dp[i] = mc;
        }
        return mc;
    }

} mc;

DLX

Dancing Link X 求精确覆盖与重复覆盖入门

Posted on

DLX算法入门文……主要说一下我对这个算法的理解。

问题描述

精确覆盖问题:

以矩阵模型介绍,给你一个矩阵,其每个格子的权值范围是 [0,1] ,让你选出若干行,使得选出的行的 1 覆盖了一行的所有格子,且不能有重叠。

重复覆盖问题:

与精确覆盖问题基本相同,但是所选的行集合中,同一列的 1 允许重叠。
这个问题当然不可能让你输出可行方案,输出的应该是行数最小的方案。

算法理解

精确覆盖和重复覆盖都是NP问题,通常的,我们只能通过搜索去解决它。事实上DLX算法也是基于搜索算法。这里放上我的学习博客,里面讲的非常详细,一般人写的博客已然不会超过他。
所以我写这个个人理解其实主要是给自己看的。

首先最容易的当然是 \( 2^{row} \) 的最简单的裸搜,这谁都想得到……而且复杂度很高……

其实当我们选中一行时,对于这一行的每一个 1 元素,含有与选中行同一列的 1 元素的行自然是不能选的,与此同时对于选中行每一个 1 元素,它所在的列其实我们也已经不再需要去考虑它们,因此,我们可以把这些元素删除,得到一个新的矩阵,如此重复操作,直到能覆盖一行的所有格子。

基本的原理就是这些,因为涉及到非常多的增删数据,使用链表是非常非常高效且合理的!!
因为给定的图一般是稀疏图,所以如果只记录 1 的位置将会非常省内存。

而对于重复覆盖,与精确覆盖基本一致,因为找最小的原因,还可以加一个 A * 优化。

入门实践与模板

HihoCoder 1317 搜索四·跳舞链

题意:
最基本的精确覆盖入门题

思路:
模板题……

而且非常意外的发现网上的模板相似度非常高!!
所以我这里也就改了一蛤变量名就没了。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string.h>
#include <string>
#include <utility>
#include <vector>

#define ll long long

using namespace std;

const int maxnode = 1e5 + 10;
const int maxm = 1e3 + 5;
const int maxn = 1e3 + 5;

struct DLX {
    int n, m, size;
    int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode]; //L,R,D,U四个数组记录某节点上下左右邻居
    int head[maxn], ccnt[maxm];                                                     //head记录排头,ccnt记录某列有多少个节点
    int ansd, ans[maxn];
    void init(int _n, int _m)
    {
        n = _n;
        m = _m;
        for (int i = 0; i <= m; i++) {
            ccnt[i] = 0;
            U[i] = D[i] = i;
            L[i] = i - 1;
            R[i] = i + 1;
        }
        R[m] = 0;
        L[0] = m;
        size = m;
        for (int i = 1; i <= n; i++)
            head[i] = -1;
    }

    void link(int r, int c)
    {
        ++ccnt[Col[++size] = c];
        Row[size] = r;
        D[size] = D[c];
        U[D[c]] = size;
        U[size] = c;
        D[c] = size;
        if (head[r] < 0)
            head[r] = L[size] = R[size] = size;
        else {
            R[size] = R[head[r]];
            L[R[head[r]]] = size;
            L[size] = head[r];
            R[head[r]] = size;
        }
    }

    void exactRemove(int c)
    {
        L[R[c]] = L[c];
        R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j]) {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                --ccnt[Col[j]];
            }
    }

    void repeatRemove(int c)
    {
        for (int i = D[c]; i != c; i = D[i])
            L[R[i]] = L[i], R[L[i]] = R[i];
    }

    void repeatResume(int c)
    {
        for (int i = U[c]; i != c; i = U[i])
            L[R[i]] = R[L[i]] = i;
    }

    int f()
    {
        bool vv[maxm];
        int ret = 0, c, i, j;
        for (c = R[0]; c != 0; c = R[c])
            vv[c] = 1;
        for (c = R[0]; c != 0; c = R[c])
            if (vv[c]) {
                ++ret, vv[c] = 0;
                for (i = D[c]; i != c; i = D[i])
                    for (j = R[i]; j != i; j = R[j])
                        vv[Col[j]] = 0;
            }
        return ret;
    }

    void repeatDance(int d)
    {
        if (d + f() >= ansd)
            return; //估价函数剪枝,A*搜索
        if (R[0] == 0) {
            if (d < ansd)
                ansd = d;
            return;
        }
        int c = R[0], i, j;
        for (i = R[0]; i; i = R[i])
            if (ccnt[i] < ccnt[c])
                c = i;
        for (i = D[c]; i != c; i = D[i]) {
            repeatRemove(i);
            for (j = R[i]; j != i; j = R[j])
                repeatRemove(j);
            repeatDance(d + 1);
            for (j = L[i]; j != i; j = L[j])
                repeatResume(j);
            repeatResume(i);
        }
    }

    void exactResume(int c)
    {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j])
                ++ccnt[Col[U[D[j]] = D[U[j]] = j]];
        L[R[c]] = R[L[c]] = c;
    }

    //d为递归深度
    bool exactDance(int d)
    {
        if (R[0] == 0) {
            ansd = d;
            return true;
        }
        int c = R[0];
        for (int i = R[0]; i != 0; i = R[i])
            if (ccnt[i] < ccnt[c])
                c = i;
        exactRemove(c);
        for (int i = D[c]; i != c; i = D[i]) {
            ans[d] = Row[i];
            for (int j = R[i]; j != i; j = R[j])
                exactRemove(Col[j]);
            if (exactDance(d + 1))
                return true;
            for (int j = L[i]; j != i; j = L[j])
                exactResume(Col[j]);
        }
        exactResume(c);
        return false;
    }

    void output()
    {
        printf("%d", ansd);
        for (int i = 0; i < ansd; i++)
            printf(" %d", ans[i]);
        puts("");
    }
};

DLX dlx;
int main()
{
    int n, m, T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        dlx.init(n, m);
        for (int i = 1, num; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                scanf("%d", &num);
                if (num == 1)
                    dlx.link(i, j);
            }
        if (!dlx.exactDance(0))
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}