三元环

HDU 6184 Counting Stars

Posted on

一个三元环计数问题……
当然是转化出来的……

一开始没想到去计数三元环的思路,而是直接搜……
然后发现题目理解错了……

又发现这特么不就跟三元环数量有关么??
巧的是薛昊之前问过我三元环计数,我还特意去看了几眼。不然真的可能卡不出来。

题意:
给你一张无向图,让你计数这样的子图。
V=(A,B,C,D) , E=(AB,BC,CD,DA,AC)

思路:
一开始我以为必须是矩形,然后发现同一点的不同三元环都满足条件。
所以我只要找到这个点的所有三元环数量,任意挑出两个即可。记得去重

个人三元环计数方法如下:
首先枚举每一条遍,再判断两个端点,确定度数较少的点,从这个点进行扩展一条边,再判断这条遍的另一端是否有边与第一条边的另一端点相连。

其中有很多细节值得优化,比如说对于\( sqrt(m) \)为分界进行不同的判定。

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 long long ll;
const int maxn = 1e5 + 5;

vector<int> G[maxn];
int link[maxn];
bool vis[maxn];

set<ll> key;
int deg[maxn];

int main()
{
    int n, m, u, v;
    while (scanf("%d %d", &n, &m) != EOF) {
        key.clear();
        for (int i = 1; i <= n; i++) {
            G[i].clear();
            link[i]=vis[i] = false;
            deg[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
            key.insert((ll)u * n + v);
            key.insert((ll)v * n + u);
            deg[u]++, deg[v]++;
        }
        int limit = sqrt(1.0 * m);
        ll ans = 0;
        for (int u = 1; u <= n; u++) {
            vis[u] = true;
            int sz = G[u].size();
            for (int i = 0; i < sz; i++)
                link[G[u][i]] = u;
            for (int i = 0; i < sz; i++) {
                int v = G[u][i];
                if (vis[v])
                    continue;
                ll sum = 0;
                if (deg[v] <= limit) {
                    int vz = G[v].size();
                    for (int j = 0; j < vz; j++) {
                        int k = G[v][j];
                        if (link[k] == u)
                            sum++;
                    }
                } else {
                    for (int j = 0; j < sz; j++) {
                        ll k = G[u][j];
                        ll val = k * n + v;
                        if (key.find(val) != key.end())
                            sum++;
                    }
                }
                ans += sum * (sum - 1) / 2;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}
欧拉图

51Nod 1967 路径定向

Posted on

首先说一下这道题的思路真的是非常巧妙。

但是,出题人脑子进shi了么,难道一定要写法和你一样才能过????

反正卡的特别紧,我到最后还有一个测试点一直超时。
时间限制是 1200s ,明显就是故意的。这种故意卡常在51Nod里巨特么多。搞不懂他们在想什么。
不觉得会在以后碰到类似的题目会故意卡我,因为很多人都是 1000 ~ 1200 的时间卡过的。

题意:
给你一个有向图,让你任意改动边的方向,使得出入度相同的点数最多。
并输出方案。

思路:
一眼看成上下界网络流。实际上这道题就是用上下界网络流改出来的,但就别想了,正解都卡着过,网络流能过?

建图方式和无汇源上下界可行流一致,跑一遍最大流即可。

下面是另一种思路。
有入度相同的特征的图还有一种,就是欧拉图,对于度数为奇数的点(以下简称奇点,反之偶点),必然不可能存在一个方案使得其出入点相同。这是必然的,那么反过来对于偶点,如果欧拉路径存在也就必然存在一个方案使得其出入度相同。
直接将所有奇点,顺序两两相连,跑一遍欧拉路径即可。

这里补充两点

  1. 奇点数量必然为偶数。因为每一条遍贡献的度数为 2 ,所以度数和为偶数。
  2. 奇点相连不会对偶点产生任何影响。

因此,我们可以得出结论,这个方案必然存在!

TLE Code

#include <stdio.h>
#include <string.h>

typedef long long ll;
const int maxn = 1e6 + 5;
const int maxm = 2e6 + 5;

namespace fastIO {
#define BUF_SIZE 100000
bool IOerror = 0;
inline char nc()
{
    static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
    if (p1 == pend) {
        p1 = buf;
        pend = buf + fread(buf, 1, BUF_SIZE, stdin);
        if (pend == p1) {
            IOerror = 1;
            return -1;
        }
    }
    return *p1++;
}
inline bool blank(char ch)
{
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int& x)
{
    char ch;
    while (blank(ch = nc()))
        ;
    if (IOerror)
        return;
    for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0')
        ;
}
#undef BUF_SIZE
};
using namespace fastIO;

struct node {
    int to, next;
} edges[maxm << 1];
int head[maxn], idx;

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

int deg[maxn];
char dir[maxn];

bool vis[maxm];

void dfs(int u)
{
    for (int id = head[u]; ~id; id = edges[id].next) {
        if (!vis[id]) {
            dir[id >> 1] = (id & 1) + '0';
            vis[id] = vis[id ^ 1] = true;
            dfs(edges[id].to);
        }
    }
}

int main()
{
    int n, m, u, v;
    read(n), read(m);
    for (int i = 0; i <= n; i++)
        head[i] = -1;
    for (int i = 0; i < m; i++) {
        read(u), read(v);
        addEdge(u, v);
        deg[u]++, deg[v]++;
    }
    int ans = 0, pre = -1;
    for (int i = 1; i <= n; i++) {
        if (deg[i] & 1) {
            if (pre == -1)
                pre = i;
            else {
                addEdge(i, pre);
                pre = -1;
            }
        } else
            ans++;
    }
    for (int i = 1; i <= n; i++)
        if (!dir[i])
            dfs(i);
    printf("%d\n", ans);
    dir[m] = 0;
    puts(dir);
    return 0;
}