状压DP

CodeForces 11D A Simple Task

Posted on

今天做的不太一样的状压,从去年的专题找的,看到学长并没有写是已经写过了么?
可能是因为跟图论相关的原因吧。

题意:
给你一个简单图,让你找出简单环的数量。
附 : 简单环就是没有重边和重点的环。
点数为 19 。

思路:
19个点,一般很容易想到状压和二维……根据数据猜算法?
事实上我是没有想到二维的

dp[ s ] [ p ] 表示 s 集合 p 为当前位置的边数 ,初始对每个状态 dp [ 1<< i ][ i ] 设置为 1
对于每一个状态,固定的从最小的一位 1 作为起点,从这个起点开始扩散,如果能回到这个起点,就进行计数。

因为对于一个环,枚举起点和终点的话,会存在起点到终点,和以终点为起点的情况。
比如说 1-> 2 -> 3 ->1 和 3 -> 2 -> 1 -> 3

AC Code

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 20;
typedef long long ll;

int map[maxn][maxn], n, m, u, v;
ll dp[1 << maxn][maxn];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        u--, v--;
        map[u][v] = map[v][u] = 1;
    }
    ll ans = 0;
    for (int i = 0; i < maxn; i++)
        dp[1 << i][i] = 1;
    for (int st = 1; st < (1 << n); st++) {
        int s = __builtin_ctz(st); //右边第一个1的位置
        for (int e = s; e < n; e++) {  //枚举集合元素 作为当前位置
            if (st & (1 << e)) {
                for (int i = s; i < n; i++) {  // 扩散状态
                    int nst = st | (1 << i);
                    if (map[e][i] && (st & (1 << i)) == 0) { //新状态
                        dp[nst][i] += dp[st][e];
                        if (map[i][s] && __builtin_popcount(nst) > 2) // 能回到起点 1的数量也就是边数大于2
                            ans += dp[st][e]; 
                    }
                }
            }
        }
    }
    printf("%lld\n", ans / 2);
    return 0;
}

状压DP

CodeForces 8 C Looking for Order

Posted on

前几天刚写了一道状压DP入门题,结果这次就遇到了,在比赛最后一点时间一眼看破,无奈只有想法,写不来……

不过赛后尝试写的时候遇到了一个自己不会的问题,也就是说假如比赛的时候开了这道题,我也会一直卡着。

题意:
给你很多个行李的位置和起点的位置,要你把所有行李搬运到起点,一次只能搬一个或者两个,花费是距离,求最小花费。行李最多24个。

思路
状压dp,对于每一个状态,我们通过dp维护其最优。
因为这里的拿取行李是与顺序无关的,那么,我通过从小到大枚举状态,在保证我当前状态最优的前提下,由我当前状态拓展而来的状态只要通过比较就可以达到最优好暴力
所以我通过枚举,找到第一个它能够搬运的行李,每次都拓展这个状态即可。

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)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int max_n = 30;
const int max_m = 1 << 24;

int n, tmp;
int dp[max_m], pre[max_m];

pii nodes[max_n];
int dis[max_n][max_n];

inline int calcul(int a, int b)
{
    return (nodes[a].first - nodes[b].first) * (nodes[a].first - nodes[b].first) + (nodes[a].second - nodes[b].second) * (nodes[a].second - nodes[b].second);
}

int main()
{
    scanf("%d %d %d", &nodes[29].first, &nodes[29].second, &n);
    nodes[n] = nodes[29];
    each(i, n) scanf("%d %d", &nodes[i].first, &nodes[i].second);
    each(i, n + 1) range(j, i + 1, n) dis[i][j] = dis[j][i] = calcul(i, j);
    fill(dp, 0x3f), dp[0] = 0;
    each(i, (1 << n)) if (dp[i] != inf) each(j, n) if (!(i & (1 << j)))
    {
        int t = (i | (1 << j));
        if (dp[t] > (tmp = dp[i] + 2 * dis[j][n])) {
            dp[t] = tmp;
            pre[t] = i;
        }
        each(k, n) if (!(t & (1 << k)))
        {
            int p = (t | (1 << k));
            if (dp[p] > (tmp = dp[i] + dis[k][n] + dis[j][n] + dis[k][j])) {
                dp[p] = tmp;
                pre[p] = i;
            }
        }
        break ;
    }
    int cur = (1 << n) - 1, ps, det;
    printf("%d\n0 ", dp[cur]);
    while (cur != 0) {
        ps = pre[cur];
        det = cur - ps;
        each(i, n) if (det & (1 << i)) printf("%d ", i + 1);
        printf("0 ");
        cur = ps;
    }
    return 0;
}
2-SAT

URAL 1382 Game with Cards

Posted on

Table of contents

题解

2-SAT 一眼题,但是很遗憾,我之前刷的专题里面没有输出可行解的题。我不知道怎么输出可行解,我个人以为,只要染色数量等于点数就是可行解。有哪里不对的么??

但我至少认可了Yasola巨巨在挑程上说的拓扑排序输出可行解的说法。

传送门

题意
有n个人手中有n张卡,每个人说两句话,有一句必定为真,有一句必定为假。说了2-sat一眼题……
两句话分别说,我自己手上是几号卡,别人手上是几号卡,保证不存在相同的陈述。

思路:
对于每两个人 i 和 j 的陈述,进行判断,如果产生矛盾,则建边。

产生矛盾是指两个的陈述,主语或者谓语有一个不同就产生了矛盾。
eg
1 号 手中有 2 号卡 < ---- > 1 号手中有 3 号卡
1 号 手中有 2 号卡 < ---- > 2 号手中有 2 号卡

两人的陈述分别是

陈述12
ai -> a[i]b[i] -> c[i]
bj -> a[j]b[j] -> c[j]

建边方式如下 a 表示 a 的 1 语句是对的 ,~a 表示 a 的 2 语句是对的

矛盾建边a1a2
b1a -> ~b , b -> ~a~a -> ~ b , b -> a
b2a -> b , ~b -> ~a~a -> b , ~b -> a

根据Yasola巨巨所说,求2-sat应该有三个常用算法

  1. 暴力法
  2. Tarjan
  3. Kosaraju

第三种算法昨天才知道,现在还没学,先贴上 1 和 2 的AC Code

暴力法

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

using namespace std;

const int maxn = 2005;

int idx, n, m, vis_time, top;
int head[maxn], st[maxn];
bool instack[maxn], vis[maxn];
int a[maxn], b[maxn], c[maxn], num[maxn];

struct node {
    int to;
    int nxt;
} edges[1005 * 1005 * 2];

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void init()
{
    for (int i = 0; i < 2 * n; i++)
        head[i] = -1;
}

void CreateGraph()
{
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j]) {
                addEdge(i << 1, j << 1 | 1);
                addEdge(j << 1, i << 1 | 1);
            }
            if (b[i] == b[j] || c[i] == c[j]) {
                addEdge(i << 1 | 1, j << 1);
                addEdge(j << 1 | 1, i << 1);
            }
            if (i + 1 == b[j] || a[i] == c[j]) {
                addEdge(i << 1, j << 1);
                addEdge(j << 1 | 1, i << 1 | 1);
            }
            if (b[i] == j + 1 || c[i] == a[j]) {
                addEdge(i << 1 | 1, j << 1 | 1);
                addEdge(j << 1, i << 1);
            }
        }
    }
}

bool dfs(int u)
{
    if (vis[u ^ 1])
        return false;
    if (vis[u])
        return true;
    vis[u] = true;
    st[top++] = u;
    for (int id = head[u]; ~id; id = edges[id].nxt)
        if (!dfs(edges[id].to))
            return false;
    return true;
}

bool solve()
{
    for (int i = 0; i < 2 * n; i += 2) {
        if (!vis[i] && !vis[i + 1]) {
            top = 0;
            if (!dfs(i)) {
                while (top)
                    vis[st[--top]] = false;
                if (!dfs(i + 1))
                    return false;
            }
        }
    }
    return true;
}

int main()
{
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", a + i, b + i, c + i);
    CreateGraph();
    if (solve())
        for (int i = 0; i < n; i++)
            printf("%d ", vis[i << 1] ? 1 : 2);
    return 0;
}

Tarjan

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

using namespace std;

const int maxn = 2005;

int idx, tpidx, n, m, scc, top, vis_time;
int head[maxn], tphead[maxn], dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn];
bool instack[maxn], vis[maxn], judge[maxn];
int a[maxn], b[maxn], c[maxn], indegree[maxn];
int crs[maxn], col[maxn];

queue<int> que;

struct node {
    int from, to;
    int next;
} edges[1005 * 1005 * 2], tp_edges[1005 * 1005 * 2];

void addEdge(int u, int v)
{
    edges[idx].from = u;
    edges[idx].to = v;
    edges[idx].next = head[u];
    head[u] = idx++;
}

void addTPEdge(int u, int v)
{
    tp_edges[tpidx].from = u;
    tp_edges[tpidx].to = v;
    tp_edges[tpidx].next = tphead[u];
    tphead[u] = tpidx++;
}

void tarjan(int u)
{
    int v;
    low[u] = dfn[u] = vis_time++;
    instack[u] = true;
    st[++top] = u;
    for (int id = head[u]; ~id; id = edges[id].next) {
        v = edges[id].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scc++;
        do {
            v = st[top--];
            instack[v] = false;
            color[v] = scc;
        } while (v != u);
    }
}

void CreateGraph()
{
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j]) {
                addEdge(i << 1, j << 1 | 1);
                addEdge(j << 1, i << 1 | 1);
            }
            if (b[i] == b[j] || c[i] == c[j]) {
                addEdge(i << 1 | 1, j << 1);
                addEdge(j << 1 | 1, i << 1);
            }
            if (i + 1 == b[j] || a[i] == c[j]) {
                addEdge(i << 1, j << 1);
                addEdge(j << 1 | 1, i << 1 | 1);
            }
            if (b[i] == j + 1 || c[i] == a[j]) {
                addEdge(i << 1 | 1, j << 1 | 1);
                addEdge(j << 1, i << 1);
            }
        }
    }
}

void topoSort()
{
    for (int i = 1; i <= scc; i++)
        if (indegree[i] == 0)
            que.push(i);
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
        if (col[cur] == 0) {
            col[cur] = 1;
            col[crs[cur]] = -1;
        }
        for (int id = tphead[cur]; ~id; id = tp_edges[id].next)
            if (--indegree[tp_edges[id].to] == 0)
                que.push(tp_edges[id].to);
    }
}

bool getAns()
{
    for (int i = 0; i < n; i++) {
        if (color[i << 1] == color[i << 1 | 1])
            return false;
        crs[color[i << 1]] = color[i << 1 | 1];
        crs[color[i << 1 | 1]] = color[i << 1];
    }
    for (int i = 0; i < idx; i++) { 
        if (color[edges[i].from] != color[edges[i].to]) {
            addTPEdge(color[edges[i].to], color[edges[i].from]);
            indegree[color[edges[i].from]]++;
        }
    }
    topoSort();
    for (int i = 0; i < n; i++)
        judge[i] = col[color[i << 1]] == 1 ? true : false;
    return true;
}

void init()
{
    while (!que.empty())
        que.pop();
    for (int i = 0; i < 2 * n; i++)
        tphead[i] = head[i] = -1;
}

int main()
{
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", a + i, b + i, c + i);
    CreateGraph();
    for (int i = 0; i < 2 * n; i++)
        if (dfn[i] == 0)
            tarjan(i);
    if (getAns())
        for (int i = 0; i < n; i++)
            printf("%d ", judge[i] ? 1 : 2);
    return 0;
}