二分图染色

洛谷 1155 双栈排序

Posted on

别多说了,神题。

写不来,看得是大佬的题解
很妙,没想到用二分图染色,但是二分图染色的模型的确很适合这个题目。

不过关键还是那个判定定理。

题意:
给你一个序列,要你用两个栈给它排序,问你这个序列是否能排序成功。

思路:
上面的链接很详细,我这里简单说一蛤。
首先必须注意到判定两个数必须在两个不同的栈的充要条件。

S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j]. 证明略过,请参考sqybi.尝试后可以发现结论P是正确的.

我们首先用\( O( n^2 ) \) 的复杂度预处理出必须在两个栈的位置,并对其连边,再对其染色,对没有限制的优先放在第一个栈中因为要字典序最小

通过染色判定,不能形成二分图则输出0,否则模拟输出序列。

#include <bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;

int ary[maxn];
int bmin[maxn];
int color[maxn];
int st1[maxn], st2[maxn], t1, t2;

vector<int> G[maxn];

bool dfs(int u, int c)
{
    color[u] = c;
    int sz = G[u].size(), v;
    for (int i = 0; i < sz; i++) {
        v = G[u][i];
        if (!color[v] && !dfs(v, 3 - c))
            return false;
        else if (color[v] == c)
            return false;
    }
    return true;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", ary + i);
    bmin[n] = inf;
    for (int i = n - 1; i >= 0; i--)
        bmin[i] = min(bmin[i + 1], ary[i]);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (ary[i] < ary[j] && bmin[j + 1] < ary[i])
                G[i].push_back(j), G[j].push_back(i);
    for (int i = 0; i < n; i++)
        if (!color[i] && !dfs(i, 1)) {
            puts("0");
            return 0;
        }
    int cur = 1;
    for (int i = 0; i < n; i++) {
        if (color[i] == 1) {
            printf("a ");
            st1[++t1] = ary[i];
        } else {
            printf("c ");
            st2[++t2] = ary[i];
        }
        while (st1[t1] == cur || st2[t2] == cur) {
            if (st1[t1] == cur)
                printf("b "), t1--;
            else
                printf("d "), t2--;
            cur++;
        }
    }
    return 0;
}
无汇源上下界可行流

ZOJ 2314 Reactor Cooling

Posted on

无汇源上下界可行流的模板题。
说是模板题,其实想让它除了二分以外加点变化也是有点困难的。

关于上下界网络流的问题,以前偷懒没学,本来打算这几天补上,加上今天薛昊这个催化剂又来问我,于是就今天开始补了。

在这里我非常非常非常非常非常推荐这篇博文
总结的非常详细,写的有十分通俗易懂,全文十分连贯,评论也有人说看完给人一种荡气回肠的感觉。
当我看完无汇源上下界可行流的时候,我马上敲了一蛤这道题,就一 A 了。妙啊!

下面简单说一下无汇源上下界可行流的解法,不详细说明,具体请看上面的链接。
无汇源上下界可行流可用建图+最大流解决,建图方式如下:

  • 对每个给定的边建边,容量为 up - down
  • 记录每个点的 down 流量差,这里设 入流量为正,出流量为负。如果总的流量差大于0,建边 src -> 该点,容量为流量差。否则,建边 该点 -> des 容量为流量差的负值。

没了,再跑一遍最大流,如果能满流就说明有可行流,否则无解。

题意:
无汇源上下界可行流裸题。

思路:
见上。

AC Code

#include <bits/stdc++.h>

using namespace std;

using namespace std;
const int maxn = 204;
const int maxm = 4e4 + 5;
const int inf = 0x3f3f3f3f;

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

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

queue<int> que;

int getNode(int a, int b) { return a * m + b; }

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);
    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 ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= des; i++)
            cur[i] = head[i];
        while ((cflow = dfs(src, inf)))
            ans += cflow;
    }
    return ans;
}

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

int deg[maxn], down[maxm];

int main()
{
    int T, u, v, up;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        init(0, n + 1);
        memset(deg, 0, sizeof deg);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d %d", &u, &v, &down[i], &up);
            addEdge(u, v, up - down[i]);
            deg[u] -= down[i], deg[v] += down[i];
        }
        int sum = 0;
        for (int i = 1; i <= n; i++)
            if (deg[i] > 0) {
                addEdge(src, i, deg[i]);
                sum += deg[i];
            } else
                addEdge(i, des, -deg[i]);
        if (dinic() < sum) {
            puts("NO");
        } else {
            puts("YES");
            for (int i = 0; i < m; i++)
                printf("%d\n", edges[i << 1 | 1].cap + down[i]);
        }
    }
    return 0;
}
LCA

POJ 3728 The merchant

Posted on

LCA 好题!

这道题我暂时只知道用Tarjan的解法。
Tarjan解法完美地运用了Tarjan的核心原理与性质:
深度优先搜索时的向下局部性。自己乱取得,蛤蛤蛤

题意:
给你一棵树,每个节点有一个权值。给你很多个询问,每个询问两个点。要你在给定点的树链上找到有序的最大差值。

思路:
首先考虑分治。设树链 u -> lca -> v
答案无非只有三种情况:

  1. u -> lca 的最大差值
  2. lca -> v 的最大差值
  3. lca -> v 的最大值 - u -> lca 的最小值

考虑dp维护这四个值。
因为运用Tarjan算法的时候,基于dfs,在你的眼里,当前节点就是向下整棵树的根节点,你完全不会去考虑往上的节点。
所以你现在使用的四个值,刚好是你当前节点的孩子节点的最优值。
基于这个事实,我们可以对其状态转移并维护。

AC Code

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int n;
int val[maxn], res[maxn];
int up[maxn], down[maxn], max_val[maxn], min_val[maxn];
int root[maxn];
bool vis[maxn];

vector<int> g[maxn];
vector<pii> q[maxn];
vector<pii> ans[maxn];

int findRoot(int x)
{
    if (root[x] == x)
        return x;
    int fa = root[x];
    root[x] = findRoot(root[x]);
    up[x] = max(up[x], max(up[fa], max_val[fa] - min_val[x]));
    down[x] = max(down[x], max(down[fa], max_val[x] - min_val[fa]));
    max_val[x] = max(max_val[x], max_val[fa]);
    min_val[x] = min(min_val[x], min_val[fa]);
    return root[x];
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    int sz = q[u].size();
    for (int i = 0; i < sz; i++) {
        int v = q[u][i].second;
        if (vis[v]) {
            int lca = findRoot(v);
            ans[lca].push_back(make_pair(u, i));
        }
    }
    sz = g[u].size();
    for (int i = 0; i < sz; i++) {
        int v = g[u][i];
        if (!vis[v]) {
            tarjan(v);
            root[v] = u;
        }
    }
    sz = ans[u].size();
    for (int i = 0; i < sz; i++) {
        int x = ans[u][i].first, y = q[x][ans[u][i].second].second;
        int id = q[x][ans[u][i].second].first;
        if (id < 0) {
            id = -id;
            swap(x, y);
        }
        findRoot(x), findRoot(y);
        res[id] = max(up[y], down[x]);
        res[id] = max(res[id], max_val[x] - min_val[y]);
    }
}

void init()
{
    for (int i = 0; i <= n; i++) {
        g[i].clear(), q[i].clear(), ans[i].clear();
        vis[i] = false;
        up[i] = down[i] = 0;
    }
}

int main()
{
    int u, v, qnum;
    while (scanf("%d", &n) != EOF) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", val + i);
            min_val[i] = max_val[i] = val[i];
        }
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        scanf("%d", &qnum);
        for (int i = 1; i <= qnum; i++) {
            scanf("%d %d", &u, &v);
            q[u].push_back(make_pair(-i, v));
            q[v].push_back(make_pair(i, u));
        }
        tarjan(1);
        for (int i = 1; i <= qnum; i++)
            printf("%d\n", res[i]);
    }
    return 0;
}
最短路

POJ 2449 Remmarguts’ Date

Posted on

K短路裸题。

这里的K短路是基于每个点只能访问一次,也就是说这个K短路必须是一条链。
再换句话说,这个K短路的K是有限制的,如果超过了这个限制,就输出 -1 。
这是和之前多校的次短路不一样的地方。

简单说一下K短路的解决思路:
首先我们应该认识到,最最简单的最短路算法是基于 bfs 改进而来,我们用 bfs 的思路继续拓展,在第一次到达终点后并不停止,而是继续 bfs 搜索,直到第K次到达终点,就是我们要求的答案。
当然,单纯的 bfs 是瞎 jb 搜,堆优化的spfa效率良好,但我们可以更进一步优化。
K短路于此之上还用了 A* 优化,先对反图 最短路遍历一遍,在正图遍历的时候,除了对起点 src 到当前距离 堆优化以外,还对当前距离进行答案估计,并将其优先级先于距离。

仔细想一想,其实很显然,不过为什么最短路不用 A* 优化呢?
因为有处理估值函数的时间,最短路都已经求完了。

题意:
K短路裸题。

思路:
见上。

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

using namespace std;

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

int idx, n, m;
int src, des;
int head[maxn], head2[maxn];
bool inq[maxn];
int dis[maxn];

struct node {
    int to, weight;
    int next;
    node(int a = 0, int b = 0, int c = 0) { to = a, weight = b, next = c; }
    bool operator<(const node& a) const { return weight > a.weight; }
} edges[maxm], redges[maxm];

struct qnode {
    int node, dist, src_dis;
    bool operator<(const qnode& a) const { return dist == a.dist ? src_dis > a.src_dis : dist > a.dist; }
} tmp;

void addEdge(int u, int v, int w)
{
    edges[idx] = node(v, w, head[u]);
    head[u] = idx;
    redges[idx] = node(u, w, head2[v]);
    head2[v] = idx++;
}

void spfa(int st)
{
    queue<int> que;
    fill(dis, dis + 1 + n, inf);
    dis[st] = 0, inq[st] = true;
    que.push(st);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        inq[u] = false;
        for (int id = head2[u]; ~id; id = redges[id].next) {
            int v = redges[id].to;
            if (dis[v] > dis[u] + redges[id].weight) {
                dis[v] = dis[u] + redges[id].weight;
                if (!inq[v]) {
                    inq[v] = true;
                    que.push(v);
                }
            }
        }
    }
}

void nthSP(int k)
{
    if (src == des)
        k++;
    priority_queue<qnode> que;
    que.push((qnode){ src, 0, 0 });
    int cnt = 0;
    while (!que.empty()) {
        tmp = que.top();
        que.pop();
        int u = tmp.node, dist = tmp.src_dis;
        if (u == des) {
            if (++cnt == k) {
                printf("%d\n", tmp.dist);
                return;
            }
        }
        for (int id = head[u]; ~id; id = edges[id].next)
            que.push((qnode){ edges[id].to, dist + edges[id].weight + dis[edges[id].to], dist + edges[id].weight });
    }
    puts("-1");
}

int main()
{
    int u, v, w, k;
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(head, -1, sizeof head), idx = 0;
        memset(head2, -1, sizeof head2);
        while (m--) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
        }
        scanf("%d %d %d", &src, &des, &k);
        spfa(des);
        nthSP(k);
    }
    return 0;
}
最大团

HDU 3585 maximum shortest distance

Posted on

淦啊……我之前自以为入门的最大团DP优化板子是错的,我说怎么和极大团计数差别这么多,那个原先的根本就是一个被谁自创的dfs+dp优化算法,速度平均慢一倍!!!

说句别的,终于刷完这套……给出链接
最大团与稳定婚姻专题

题意:
要你找出一个数量不小于 k 的最大团,使得最大团中的最短距离最大。

思路:
二分距离+最大团判定

老实说我一开始没想到,但看到这个思路之后就是豁然开朗,感觉二分的思路都是这样的……
然后疯狂TLE……不知道为什么,查了一下,最大团板子太慢了……原来学得是民间算法!!

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#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 maxn = 55;

int n, k, ans;
pii point[maxn];
int some[maxn][maxn], dis[maxn][maxn];
int len[maxn * maxn], alimit;

inline int two(int x) { return x * x; }

int calc(int a, int b)
{
    return two(point[a].first - point[b].first) + two(point[a].second - point[b].second);
}

bool dfs(int deep, int sn, int an)
{
    if (an >= k)
        return true;
    if (sn + an < k)
        return false;
    int u = some[deep][1];
    range(i, 1, sn)
    {
        int v = some[deep][i];
        if (dis[u][v] >= alimit)
            continue;
        int tsn = 0;
        range(j, 1, sn) if (dis[v][some[deep][j]] >= alimit) some[deep + 1][++tsn] = some[deep][j];
        if (dfs(deep + 1, tsn, an + 1))
            return true;
        some[deep][i] = 0;
    }
    return false;
}

bool check(double limit)
{
    range(i, 1, n) some[1][i] = i;
    alimit = limit;
    return dfs(1, n, 0);
}

int main()
{
    while (scanf("%d %d", &n, &k) != EOF) {
        range(i, 1, n) scanf("%d %d", &point[i].first, &point[i].second);
        int num = 0;
        range(i, 1, n) range(j, i + 1, n)
        {
            dis[i][j] = dis[j][i] = calc(i, j);
            len[num++] = dis[i][j];
        }
        sort(len, len + num);
        int l = 0, r = num - 1, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (check(len[mid]))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%.2f\n", sqrt(len[l - 1]));
    }
    return 0;
}
最大团

POJ 2989 All Friends

Posted on

最大团问题之极大团计数。

啊呀啊呀,基本都会是板子题啦……
但是尽管是板子题,上次ccpc网络赛卡我的题,我当时要是有个最大团的板子,就可以直接过了……

极大团计数和最大团不大一样,这里有wiki上的伪代码

BronKerbosch(All, Some, None):
if Some and None are both empty:
report All as a maximal clique //所有点已选完,且没有不能选的点,累加答案
for each vertex v in Some: //枚举Some中的每一个元素
BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v))
//将v加入All,显然只有与v为朋友的人才能作为备选,None中也只有与v为朋友的才会对接下来造成影响
Some := Some - {v} //已经搜过,在Some中删除,加入None
None := None ⋃ {v}

其实就是一个优化过的回溯算法……最大团是NP问题,没办法,过几天会去学一下随机化吧。

题意:
极大团计数裸题,给你\( n \)个点,\( m\)条边,问你极大团数量。

思路:
具体看上面的伪代码。

值得注意的是,使用板子的时候格外要注意,边界外的邻接矩阵不能设置为 true ,不然会出错。不具体解释。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#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;

const int maxn = 130;

int ans;
bool g[maxn][maxn];
int some[maxn][maxn], none[maxn][maxn];
int all[maxn][maxn];

void dfs(int cur, int sz, int sn, int nn)
{
    if (!sn && !nn)
        ans++;
    if (ans > 1000)
        return;
    int key = some[cur][1];
    range(i, 1, sn)
    {
        int v = some[cur][i], tsn = 0, tnn = 0;
        if (g[key][v])
            continue;
        range(j, 1, sz) all[cur + 1][j] = all[cur][j];
        all[cur + 1][sz + 1] = v;
        range(j, 1, sn) if (g[v][some[cur][j]]) some[cur + 1][++tsn] = some[cur][j];
        range(j, 1, nn) if (g[v][none[cur][j]]) none[cur + 1][++tnn] = none[cur][j];
        dfs(cur + 1, sz + 1, tsn, tnn);
        some[cur][i] = 0, none[cur][++nn] = v;
    }
}

int main()
{
    int u, v, n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        fill(g, false), ans = 0;
        while (m--) {
            scanf("%d %d", &u, &v);
            g[u][v] = g[v][u] = true;
        }
        range(i, 1, n) some[1][i] = i;
        dfs(1, 0, n, 0);
        if (ans > 1000)
            puts("Too many maximal sets of friends.");
        else
            printf("%d\n", ans);
    }
    return 0;
}
强联通分量

HDU 6165 FFF at Valentine

Posted on

好烦,感觉自己的图论知识都有了,但是一旦写起来还是非常欠缺……
什么时候我才能踩完所有的坑,成就大佬之路呢……

今天多校的第二道签到题……
是的,签到题……但是我没有写出来为什么呢……我也想知道为什么我老是会这样那样的地方写错……

今天错的地方是没有去重,还像条疯狗一样跑去BC官方博客理论了……
在这里先道个歉……
但是题解的确没写清楚

题意:
给你一个有向图,有环,无重边,无自环。
问你是否存在两个不联通的点。

思路:
拿到题的第一思路,拓扑排序,有环就缩点呗!
然后开始疯狂WA……

思路没错,但是在缩点后没有去重,导致缩点后一条边的出度增加,拓扑排序失败……

好烦……讲道理缩点+拓扑,虽然简单,但也没有沦落到这种比赛的签到题上……

原因就是数据很小,允许 \( O ( n^2 ) \)解题……
可能因为图论学傻了,没想到也不愿意用暴力做……

暴力的方法是,枚举每一个点,记录它可以达到的点,构成一个二维矩阵,然后遍历一下矩阵,看是否存在相互不可达的点即可。
虽然暴力在我眼里有点不齿,但是优雅的暴力还是非常值得认可的。

缩点 + 拓扑排序 AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

const int maxn = 1005;

int idx, n, m, scc, top, vis_time;
int head[maxn], dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn];
bool instack[maxn];

struct node {
    int to;
    int nxt;
} edges[7000];

bool g[maxn][maxn];
int deg[maxn];
int vex[maxn];

bool toposort()
{
    for (int i = 1; i <= scc; i++)
        for (int j = 1; j <= scc; j++)
            g[i][j] = false;
    for (int u = 1; u <= n; u++) {
        int cu = color[u];
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int cv = color[edges[id].to];
            if (cu != cv && !g[cu][cv]) { //这里要去重!!!
                deg[cv]++;
                g[cu][cv] = true;
            }
        }
    }
    queue<int> que;
    for (int i = 1; i <= scc; i++)
        if (deg[i] == 0)
            que.push(i);
    while (!que.empty()) {
        if (que.size() > 1)
            return true;
        int u = que.front();
        que.pop();
        for (int i = 1; i <= scc; i++) {
            if (g[u][i]) {
                if (--deg[i] == 0)
                    que.push(i);
            }
        }
    }
    return false;
}

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

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].nxt) {
        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 init()
{
    for (int i = 0; i <= n; i++) {
        head[i] = -1;
        deg[i] = in[i] = dfn[i] = low[i] = 0;
    }
    vis_time = top = idx = scc = 0;
}

int main()
{
    int T, u, v;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        init();
        while (m--) {
            scanf("%d %d", &u, &v);
            addEdge(u, v);
        }
        for (int i = 1; i <= n; i++)
            if (dfn[i] == 0)
                tarjan(i);
        if (toposort())
            puts("Light my fire!");
        else
            puts("I love you my love and our love save us!");
    }
    return 0;
}