無方向図の中の3元の環の個数を求めます

11478 ワード

無方向図は疎図、点数n<105、辺数mまず考えられる方法は暴力で解くしかない.直接的な暴力は各辺を列挙し、1辺の度数の小さい端点でもう1辺を列挙し、それから1辺の始点と2辺の終点の間に1辺があるかどうかを見て、最後に3を除く.複雑度O(m∗m−−−√).もちろんこれは重さを判断しない書き方で、重さを判断すると複雑度がO(m∗m√3)に下がることができます.
ここでは,複雑度がO(m∗m−−√)よりも高いように見えるが,実際には複雑度がO(m∗m−−√)の暴力的な方法であるが,実際には多くの不必要な判断を減らすことができる方法を紹介する.まず、この図にx個の点があり、完全図(各点にエッジが接続されている、すなわち、1つの点から発せられた任意の2つのエッジがメタリングを構成できる)である理想的な状況を想定すると、この図の辺数は(2 x)=m、x=m−−√であるが、問題の点がnであると、xより大きいかxより小さいか、x以下の点があるので、まずx以下の点を考慮すると、これらの点は暴力的に列挙され、度数がxより大きい点連辺または同じ度数がxより小さい点連辺である.次に、度数がxより大きい点を考慮し、xより小さい点からxより大きい点へのエッジを暴力的に列挙したが、より大きい点については、これらの点セットの内部暴力で2つのエッジを列挙した.これでこのアルゴリズムは完成しました.
複雑度分析:
第1のクラスの点の3元の環について、列挙する時1つの点から2つの辺を列挙するので、この点の度はまたxより小さいので、1つの辺は最大x回列挙されて、最大はmの辺を列挙するので、第1のクラスの点の複雑度はmxです.
第2のクラス点の三元リングでは、第2のクラス点は最大x個であるため、列挙集合の3つの点複雑度はx 3である.
したがって,最終的な複雑度はO(m∗m−−√)である.
注意、hashの時に私が使っていたのはsetで、タイムアウトしました.set赤と黒の木で書かれているので、検索の複雑さはO(logn)なので、定数で最適化し、自分でhashを手書きしたり、C++11の新しい特性を使ったりすることができます–unordered_set、unordered_sethash表で実現されているので、検索の複雑さはO(1)であり、同様にunordered_setでは秩序が保証されませんが、ここでは大丈夫です.
次は2つの暴力的な方法コードを貼りましょう(1つ目は3 msの期限でタイムアウトし、2つ目は過ぎました).
1:

#include 
#include 

#include 

using namespace std;

using namespace std::tr1;

#define MAX_LINE 100005

typedef long long LL;

typedef struct tagEdge {
    LL src, des, next;
}Edge;

Edge e[MAX_LINE * 2];
int head[MAX_LINE];
int num_e;

int D[MAX_LINE];

int n, m;

unordered_set st;
unordered_set used;

void add_edge(int src, int des)
{
    e[num_e].src = src;
    e[num_e].des = des;
    e[num_e].next = head[src];
    head[src] = num_e++;
}

void ssort(LL &s, LL &m, LL &d)
{
    LL tmp = s + m + d;
    LL ts = min(min(s, m), d);
    LL td = max(max(s, m), d);
    s = ts, d = td, m = tmp - s - d;
}

LL work()
{
    LL ans = 0;
    for (int i = 0; i < num_e; i++) {
        if (!(i & 1) && D[e[i].des] > D[e[i + 1].des])
            continue;
        int src = e[i].src, des = e[i].des;
        for (int j = head[des]; j + 1; j = e[j].next) {
            if (e[j].des == src)
                continue;
            LL sss = src, mmm = des, ddd = e[j].des;
            ssort(sss, mmm, ddd);
            if (st.find(sss * MAX_LINE * MAX_LINE + mmm * MAX_LINE + ddd) != st.end())
                continue;

            LL ss = src;
            LL dd = e[j].des;
            if (ss > dd)
                swap(ss, dd);
            if (st.find(ss * MAX_LINE + dd) != st.end())
                ++ans, st.insert(sss * MAX_LINE * MAX_LINE + mmm * MAX_LINE + ddd);
        }
    }
    return ans;
}

int main()
{
    int T;
    for (scanf("%d", &T); T--;) {
        scanf("%d%d", &n, &m);
        memset(head, -1, sizeof(head));
        memset(D, 0 , sizeof(D));
        num_e = 0;
        st.clear();
        used.clear();

        LL src, des;
        for (int i = 0; i < m; i++) {
            scanf("%lld%lld", &src, &des);
            ++D[src], ++D[des];
            if (src > des)
                swap(src, des);
            st.insert(src * MAX_LINE + des);
            add_edge(src, des),
            add_edge(des, src);
        }

        printf("%lld
", work());
    }
    return 0;
}

/**************************************************************
    User: FlushHip
    Language: C++
    Result:     
****************************************************************/

#include 
#include 
#include 

#include 
#include 

using namespace std;

using namespace std::tr1;

#define MAX_LINE 100005

typedef long long LL;

int D[MAX_LINE];

int n, m;

unordered_set st;
vector<int> e[MAX_LINE];
vector<int> dy;

int main()
{
    int T;
    for (scanf("%d", &T); T--;) {
        scanf("%d%d", &n, &m);
        memset(D, 0 , sizeof(D));
        st.clear();
        dy.clear();
        for (int i = 0; i < MAX_LINE; i++)
            e[i].clear();

        int src, des;
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &src, &des);
            ++D[src], ++D[des];
            st.insert(1LL * src * MAX_LINE + des);
            st.insert(1LL * des * MAX_LINE + src);
            e[src].push_back(des);
            e[des].push_back(src);
        }

        LL ans = 0;

        int top = sqrt((double)m);

        for (int i = 1; i <= n; i++)
            if (D[i] <= top) {
                for (int j = 0; j < e[i].size(); j++)
                    if (D[e[i][j]] > top || e[i][j] >= i)
                        for (int k = j + 1; k < e[i].size(); k++)
                            if (D[e[i][k]] > top || e[i][k] >= i)
                                if (st.find(1LL * e[i][j] * MAX_LINE + e[i][k]) != st.end())
                                    ++ans;
            } else {
                dy.push_back(i);
            }

        for (int i = 0; i < dy.size(); i++)
            for (int j = i + 1; j < dy.size(); j++)
                if (st.find(1LL * dy[i] * MAX_LINE + dy[j]) != st.end())
                    for (int k = j + 1; k < dy.size(); k++)
                        if (st.find(1LL * dy[i] * MAX_LINE + dy[k]) != st.end() &&
                            st.find(1LL * dy[k] * MAX_LINE + dy[j]) != st.end())
                            ++ans;

        printf("%lld
", ans);
    }
    return 0;
}

/**************************************************************
    Problem: 1187
    User: FlushHip
    Language: C++
    Result:   
    Time:2572 ms
    Memory:15332 kb
****************************************************************/

rtfファイルをhtmlに変換する方法

図論-最短経路-floyd