图算法和图模型(八)

这篇博文主要讲述一下状态图，隐式图建图的技巧
补充了一些最短路的拓展
$spfa()$ 求最长路算法等等

spfa求最长路

UVALive3310

$\textbf{algorithm}$

• $\textbf{run} \ \quad \text{strongConnected?} \leftarrow \text{tarjan()}$
  $~~~~~~$$\textbf{if} \ \textbf{circle,} \ \text{ return } \infty$

• $\textbf{run} \ \text{spfa()}$
  $~~~~~~$$\textbf{relax} \ (x, y), \quad d(y) < d(x) + w(x, y)$
  $~~~~~~$$\text{get longest path}$

const int maxn = 100000+5;
const int inf = 1e9;
int n, tot;
int ans;

// == Graph definition ==
int m = 0;

class Edge {
public:
    int to, weight, s, t;
    bool loop;
    Edge *next;
    Edge() {}
    Edge(int v, int w, int s, int t, bool loop) : to(v), weight(w), s(s), t(t), loop(loop) {
        next = NULL;
    }
} edges[maxn << 1], *head[maxn];

void add(int x, int y, int w, int s, int t, bool loop) {
    edges[++m] = Edge(y, w, s, t, loop);
    edges[m].next = head[x];
    head[x] = &edges[m];
}

int dfn[maxn], low[maxn];
int belong[maxn], ccnum[maxn];
int cc = 0;
int ins[maxn];
stack<int> stk;
int clk = 0;

void initG() {
    memset(head, 0, sizeof(head));
    m = clk = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(ins, 0, sizeof(ins));
    while (stk.size()) stk.pop();

    memset(ccnum, 0, sizeof(ccnum));
    cc = 0;
    memset(belong, 0, sizeof(belong));
}

void tarjan(int u) {
    low[u] = dfn[u] = ++clk;
    stk.push(u);
    ins[u] = 1;
    for(const Edge *e = head[u]; e; e = e->next) {
        int v = e->to;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(ins[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if(dfn[u] == low[u]) {
        cc++;
        while (true) {
            int x = stk.top();
            stk.pop();
            ins[x] = false;
            belong[x] = cc;
            if(x == u) break;
        }
    }
}
// == Graph finished ==


// == build graph, important ==
const int maxl = 82;
char buf[maxl];
char Cmd[maxn][maxl];

ll nxt[maxn], len[maxn];
bool Die[maxn], vis[maxn];
int ID[maxn], pos[maxn];

void initbuild() {
    memset(ID, -1, sizeof(ID));
    memset(pos, -1, sizeof(pos));
    memset(Die, 0, sizeof(Die));
    memset(nxt, -1, sizeof(nxt));
    memset(len, 0, sizeof(len));
}

bool judge(const int u, int &v, int &w) {
    memset(vis, 0, sizeof(vis));
    vis[u] = 1;
    bool loop = false;

    while (ID[v] == -1) {
        vis[v] = 1;
        w += len[v];
        v = nxt[v];

        if(vis[v]) {
            loop = true;
            break;
        }
    }
    return loop;
}

void build() {
    initbuild();
    ID[0] = ++tot;
    pos[tot] = 0;

    _for(i, 0, n) {
        if(Cmd[i][0] == 'l') {
            int s = -1, t = -1;
            sscanf(Cmd[i], "%*s%d%d", &s, &t);
            s--;

            if(ID[s] == -1) {
                ID[s] = ++tot;
                pos[tot] = s;
            }
            if(ID[i] == -1) {
                ID[i] = ++tot;
                pos[tot] = i;
            }

            nxt[i] = i;
        }
        else if(Cmd[i][0] == 'i' || Cmd[i][0] == 'j') {
            int v;
            sscanf(Cmd[i], "%*s%d", &v);
            v--;

            if(Cmd[i][0] == 'i' && ID[i] == -1) {
                ID[i] = ++tot;
                pos[tot] = i;
            }

            nxt[i] = v;
        }
        else if(Cmd[i][0] == 'd') {
            if(ID[i] == -1) {
                ID[i] = ++tot;
                pos[tot] = i;
            }
            Die[ID[i]] = true;
            nxt[i] = i;
        }
        else {
            nxt[i] = (i + 1) % n;
        }

        len[i] = nxt[i] == i ? 0 : 1;
    }

    _forDown(i, tot, 1) {
        if(Die[i]) continue;

        int u = pos[i];
        int v = nxt[u];
        int w = len[u];

        bool lp = judge(u, v, w);
        if(lp) {
            add(ID[u], ID[u], inf, -1, -1, false);
            continue;
        }

        len[u] = w;
        nxt[u] = v;
        if(v != u) {
            add(ID[u], ID[v], w, -1, -1, false);
        }
        if(Cmd[u][0] == 'j') continue;

        // then deal with pass, loop, ifgo
        // just one step
        v = (u + 1) % n;
        w = 1;
        lp = judge(u, v, w);
        if(lp) {
            add(ID[u], ID[u], inf, -1, -1, false);
            continue;
        }

        int s = -1, t = -1;
        if(Cmd[u][0] == 'l') {
            sscanf(Cmd[u], "%*s%d%d", &s, &t);
            s--;
        }
        add(ID[u], ID[v], w, ID[s], t, Cmd[u][0] == 'l');
    }
}
// == build finished ==

// == spfa get longest path ==
ll cnt[maxn], D[maxn];
int inq[maxn];

void initspfa() {
    memset(cnt, 0, sizeof(cnt));
    memset(inq, 0, sizeof(inq));
    memset(D, 0, sizeof(D));
}

void spfa() {
    initspfa();

    queue<int> que;
    int st = ID[0];
    inq[st] = 1;
    D[st] = 1;
    que.push(st);

    while (que.size()) {
        int x = que.front();
        que.pop();
        inq[x] = false;

        if(Die[x] && ans < D[x]) ans = D[x];
        for(const Edge *e = head[x]; e; e = e->next) {
            int y = e->to;
            int w = e->weight;
            if(e->loop) w += (D[x] - D[e->s] + 1) * (e->t - 1);

            if(D[y] < D[x] + w) {
                D[y] = D[x] + w;
                if(!inq[y]) {
                    inq[y] = true;
                    que.push(y);

                    if(++cnt[y] > tot) {
                        printf("infinity\n");
                        return;
                    }
                }
            }
        }
    }
    if(ans > inf) printf("infinity\n");
    else cout << ans << endl;
}
// == spfa finished ==

// == get cmd ==
void getCmd() {
    _for(i, 0, strlen(buf)) buf[i] = tolower(buf[i]);
    char *p = strtok(buf, " ");
    while (p) {
        strcat(Cmd[n], p);
        strcat(Cmd[n], " ");
        p = strtok(NULL, " ");
    }
    n++;
}

bool cmdModify() {
    bool die = false;
    _for(i, 0, n) {
        if(Cmd[i][0] == 'd') die = true;
        if(Cmd[i][0] == 'i' || Cmd[i][0] == 'j') {
            int v;
            sscanf(Cmd[i], "%*s%d", &v);
            v--;

            if(v == (i + 1) % n) Cmd[i][0] = 'p';
            if(i == v && !die) return false;
        }
    }
    return die;
}
// == get cmd finished ==

void init() {
    memset(Cmd, 0, sizeof(Cmd));
    n = tot = 0;
}

void test() {
    _for(i, 0, n) debug(Cmd[i]);
}

int main() {
    freopen("input.txt", "r", stdin);
    while (fgets(buf, sizeof(buf) / sizeof(buf[0]), stdin)) {
        if(buf[0] == '\n') break;
        init();
        getCmd();

        while (fgets(buf, sizeof(buf) / sizeof(buf[0]), stdin)) {
            if(buf[0] == '\n') break;
            _for(i, 0, strlen(buf)) if(isspace(buf[i])) buf[i] = ' ';
            getCmd();
        }
        // one test case finished
        //test();
        if(!cmdModify()) {
            printf("infinity\n");
            continue;
        }

        // then build graph
        initG();
        build();

        bool circle = false;
        tarjan(1);
        _rep(i, 1, tot) ccnum[belong[i]]++;
        _rep(i, 1, cc) if(ccnum[i] > 1) {
            circle = true;
            break;
        }

        if(circle) {
            printf("infinity\n");
            continue;
        }

        ans = -1;
        spfa();
    }
}

有向无环图最长路径

$\textbf{dp} \ \textbf{+} \ \textbf{topoSort}$ 可解决有向无环图最长路径问题

2017Urmuqi

const int maxn = 100000 + 10;
int ans = 0;

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
    int to, weight;
    Edge() {}
    Edge(int v, int w) : to(v), weight(w) {}
};

vector<Edge> edges;
int deg[maxn];

void initG() {
    Set(deg, 0);
    _for(i, 0, maxn) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(v, w));
    G[u].push_back(edges.size() - 1);
    deg[v]++;
}

int n, m;
// == Graph finished ==

int D[maxn];
void initdp() {
    ans = 0;
    Set(D, 0);
}

void dp() {
    queue<int> que;
    _rep(i, 1, n) if(deg[i] == 0) que.push(i);

    while (que.size()) {
        int x = que.front();
        que.pop();

        if(G[x].size() == 0) ans = max(ans, D[x]);

        _for(i, 0, G[x].size()) {
            const Edge& e = edges[G[x][i]];
            int y = e.to;

            if(D[y] < D[x] + e.weight) D[y] = D[x] + e.weight;
            if(--deg[y] == 0) que.push(y);
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    scanf("%d", &kase);

    while (kase--) {
        initG();
        scanf("%d%d", &n, &m);
        _rep(i, 1, m) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addEdge(u, v, w);
        }


        initdp();
        dp();
        printf("%d\n", ans);
    }
}

二分图初步

codeforces

const int maxn = 1e5 + 10;
int n, m, k;

// == Graph ==
vector<int> G[maxn];

class Edge {
public:
    int to, weight;
    Edge() {}
    Edge(int v, int w) : to(v), weight(w) {}
};

vector<Edge> edges;

void initG() {
    _for(i, 0, maxn) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(v, w));
    G[u].push_back(edges.size() - 1);
}
// == Graph finished ==


// == solve ==
int D[maxn];
int pre[maxn];
int vis[maxn];
int bin[maxn];

void dfs(int u, int pa) {
    vis[u] = 1;
    _for(i, 0, G[u].size()) {
        const Edge& e = edges[G[u][i]];
        int v = e.to;

        if(vis[v] && v != pa) {
            vector<int> path;

            int cu = u;
            while (cu != v) {
                path.push_back(cu);
                cu = pre[cu];
            }
            path.push_back(v);

            cout << 2 << "\n";
            printf("%d\n", (int)path.size());
            for(auto x : path) printf("%d ", x);
            exit(0);
        }
        else if(!vis[v]) {
            bin[v] = bin[u] ^ 1;
            pre[v] = u;
            dfs(v, u);
        }
    }
}
// == solve finished ==

void init() {
    Set(D, 0);
    Set(pre, 0);
    Set(vis, 0);
    Set(bin, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    initG();
    init();
    scanf("%d%d%d", &n, &m, &k);
    n = k;

    _for(i, 0, m) {
        int u, v;
        scanf("%d%d", &u, &v);
        if(u > n || v > n) continue;
        addEdge(u, v, 1);
        addEdge(v, u, 1);
    }

    // solve
    _rep(i, 1, n) if(!vis[i]) {
            dfs(i, -1);
        }

    vector<int> ans[2];
    _rep(i, 1, n) {
        ans[bin[i]].push_back(i);
    }

    if(ans[0].size() < ans[1].size()) swap(ans[0], ans[1]);
    ans[0].resize((k + 1) / 2);

    cout << 1 << "\n";
    for(auto x : ans[0]) printf("%d ", x);
}