Codechef 12.5 TICKETS 图论+最短路+LCA

shinbokuow posted @ 9 年前 in Something with tags 图论最短路 LCA , 1188 阅读

题目大意：

有

$n$ 道菜和

$m$ 个顾客，每个顾客都喜欢

$n$ 道菜中不同的两种菜，现在要将这些菜供应给顾客，每道菜最多只能供应给一个顾客。现在要求最大化

$k$ ，使得在

$m$ 个顾客中任选

$k$ 个顾客都能够存在一种供应方案使得每个顾客都至少被供应到一道喜欢的菜。

数据范围：数据组数

$T\leq{15}$ ，

$2\leq{n}\leq{200},0\leq{m}\leq{500}$ 。

算法讨论：

我们考虑构造一个无向图，对于每个顾客都看成是在无向图中两道菜对应的点之间连的一条无向边。

这样的话，对于一种顾客的选择如果存在满足要求的方案，当且仅当这些边以及这些边相关的点形成的子图中点数不小于边数。

那么事实上只需求出边数最小的边数大于点数的子图就行了。

我们考虑边数最小的这种子图使得边数

$>$ 点数，若边数

$\geq$ 点数

$+2$ ，那我们考虑删去一条边，如果这删去了两个点，证明这条边与剩下的图是不连通的，且剩下的图满足边数

$>$ 点数且边数更小；如果这删去了一个点，边数和点数同时减少了1，剩下的图依然满足边数

$>$ 点数且边数更小；如果这没有删去任何点，边数减少1，剩下的图依然满足边数

$\geq$ 点数+1即边数

$>$ 点数，且边数更少。

所以我们证明了边数最小的使得边数

$>$ 点数的子图必定满足边数

$=$ 点数+1。

考虑这种子图有什么性质：

通过刚才的讨论我们已经证明这个子图中所有点的度数都至少为

$2$ ，不然就可以删掉一条边了。

令点数为

$|V|$ ，由于总度数为

$2|V|+2$ ，那么就有两种情况：

情况1：两个点度数为

$3$ ，剩下的所有点度数为

$2$ 。

这种情况要么是两个点之间有三条点不相交的路径（A），要么是两个点不相交的环上连了一条边（B）。

情况2：一个点度数为

$4$ ，剩下的所有点度数为

$2$ 。

这种情况只能是两个环只同时存在一个点（C）。

对于A，我们枚举所有起点和终点求出最短的三条路径就行了，时间复杂度

$O(n^2m)$ 。

对于B，C，我们可以枚举根做一棵有根树，再枚举所有非树边，得到这条非树边构成的环和路径的总长，然后只需要维护总长的最小值和次小值用总和来更新答案即可。最小值和次小值的路径相交是没有关系的，因为如果相交那么说明在A中一定能求出更小的解。实现中用LCA来求路径的长度，我们暴力

$O(n)$ 来求，总时间

$O(n^2m)$ 。

时空复杂度：

时间复杂度

$O(Tn^2m)$ ，空间复杂度

$O(m)$ 。

代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define N 210
#define M 510
int n, m;
int head[N], nxt[M << 1], to[M << 1], ind;
void reset() {
    ind = 0;
    memset(head, -1, sizeof head);
}
void addedge(int a, int b) {
    int q = ind++;
    to[q] = b;
    nxt[q] = head[a];
    head[a] = q++;
}
void make(int a, int b) {
    addedge(a, b);
    addedge(b, a);
}
int path3(int s, int t) {
    static int q[N], d[N], fr, ta, i, j, ans, num;
    fr = ta = 0;
    memset(d, -1, sizeof d);
    d[q[ta++] = s] = 0;
    num = ans = 0;
    while (fr != ta) {
        i = q[fr++];
        for (j = head[i]; j != -1; j = nxt[j]) {
            if (to[j] == t) {
                ans += d[i] + 1;
                if (++num == 3)
                    return ans;
            }
            else if (d[to[j]] == -1)
                d[q[ta++] = to[j]] = d[i] + 1;
        }
    }
    return inf;
}
int pa[N], dep[N], tree_edge[M << 1];
int lca(int x, int y) {
    while (x != y) {
        if (dep[x] > dep[y])
            x = pa[x];
        else
            y = pa[y];
    }
    return x;
}
int pathLinkTwoCircle(int x) {
    int i, j;
    static int q[N], fr, ta;
    memset(dep, -1, sizeof dep);
    memset(tree_edge, 0, sizeof tree_edge);
    dep[x] = 0;
    pa[x] = -1;
    fr = ta = 0;
    q[ta++] = x;
    while (fr != ta) {
        i = q[fr++];
        for (j = head[i]; j != -1; j = nxt[j]) {
            if (dep[to[j]] == -1) {
                tree_edge[j] = tree_edge[j ^ 1] = 1;
                dep[q[ta++] = to[j]] = dep[pa[to[j]] = i] + 1;
            }
        }
    }
    int mn = inf, _mn = inf, temp;
    for (i = 1; i <= n; ++i) {
        if (dep[i] == -1)
            continue;
        for (j = head[i]; j != -1; j = nxt[j]) {
            if (dep[to[j]] == -1)
                continue;
            if (!tree_edge[j]) {
                tree_edge[j] = tree_edge[j ^ 1] = 1;
                temp = dep[i] + dep[to[j]] - dep[lca(i, to[j])] + 1;
                if (temp < mn) {
                    _mn = mn;
                    mn = temp;
                }
                else if (temp < _mn)
                    _mn = temp;
            }
        }
    }
    return mn + _mn;
}
int main() {
    int T;
    cin >> T;
    int i, j, a, b;
    while (T--) {
        reset();
        cin >> n >> m;
        for (i = 1; i <= m; ++i) {
            scanf("%d%d", &a, &b);
            make(a, b);
        }
        int ans = m;
        for (i = 1; i <= n; ++i)
            for (j = i + 1; j <= n; ++j)
                ans = min(ans, path3(i, j) - 1);
        for (i = 1; i <= n; ++i)
            ans = min(ans, pathLinkTwoCircle(i) - 1);
        cout << ans << endl;
    }
    return 0;
}

Codechef 12.5 TICKETS 图论+最短路+LCA

search

lastest comments

friend links

visitor counter