Havel

HDU 2454 Degree Sequence of Graph G

Posted on

Havel定理判定简单图

被上下界网络流烦傻了,暂时不想写代码太长的题。

虽然是一道水题,但也是建立在一定理论基础上的。

再科普一下简单图,没有重边没有自环的图就是简单图。区别有向图和无向图,也就是说,有向图的反向边不算重边。

给定一个非负整数序列{dn},若存在一个无向图使得图中各点的度与此序列一一对应,则称此序列可图化。进一步,若图为简单图,则称此序列可简单图化

可图化的判定:

\( \sum_{i=1}^{n}d_{i} mod 2 == 0 \) 。关于具体图的构造,我们可以简单地把奇数度的点配对,剩下的全部搞成自环。

可简单图化的判定(Havel定理):

把序列排成不增序,即 \( d_1 \geq d_2 \geq \ldots \geq d_n \),则d可简单图化当且仅当
\( d' = \left{ d_2-1 , d_3-1 \ldots d_{d_1+1}-1 , d_{d_1+2} , d_{d_1+3} , \ldots d_n \right} \) 可简单图化。简单的说,把d排序后,找出度最大的点( 设度为\( d_1\) ),把它与度次大的d1个点之间连边,然后这个点就可以不管了,一直继续这个过程,直到建出完整的图,或出现负度等明显不合理的情况。

题意:
题目很长……没怎么看,就是给你几个点,再给你每个点的度数,问你能否构成简单图。

思路:
裸题,按照定理模拟一下即可。

#include <bits/stdc++.h>

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

int deg[maxn];

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        bool flag = true;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", deg + i);
            sum += deg[i];
            if (deg[i] >= n)
                flag = false;
        }
        if (sum & 1)
            flag = false;
        if (!flag) {
            puts("no");
            continue;
        }
        for (int i = 0; i < n; i++) {
            sort(deg + i, deg + n, greater<int>());
            int d = deg[i];
            if (d < 0 || i + d >= n) {
                flag = false;
                break;
            }
            for (int j = 1; j <= d; j++)
                deg[i + j]--;
        }
        puts(flag ? "yes" : "no");
    }
    return 0;
}
二分图染色

洛谷 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;
}