最近看见一个省队集训的课件…那就做一做吧…

APIO2008 免费道路

之前做过这种求有限制条件生成树的题…自己赋一下边权就好了

按照先选收费的边来生成一棵树, 这样就可以确定哪些免费边非选不可, 然后把这些边加入生成树中, 再随便挑点免费边加进去凑够$k$个, 然后再加收费边凑成生成树就好了

讲个鬼故事我一开始以为他要求一个子图, 结果他让求生成树…

所以我想裱讲课的人

...GG

/**************************************************************
    Problem: 3624
    User: Cansult
    Language: C++
    Result: Accepted
    Time:304 ms
    Memory:4540 kb
****************************************************************/

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN (200000 + 5)
#define MAXM (100000 + 5)
using namespace std;
struct edg
{
    int from, to, cost, bh;
}b[MAXM];
int fa[MAXN], n, m, k;
int find(int x)
{ return (x == fa[x] ? x : (fa[x] = find(fa[x]))); }
void uni(int x, int y)
{ fa[find(x)] = find(y); }
bool cmp1(edg x, edg y)
{ return x.cost > y.cost; }
bool cmp2(edg x, edg y)
{ return x.cost < y.cost; }
void solve()
{
    vector<edg> chosen;
    sort(b + 1, b + m + 1, cmp1);
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    int cntb = 0, cntk = 0;
    for (int i = 1; i <= m; i++)
    {
        if (find(b[i].from) != find(b[i].to))
        {
            ++cntb;
            uni(b[i].from, b[i].to);
            if (!b[i].cost)
                chosen.push_back(b[i]);
        }
        if (cntb == n - 1)
            break ;
    }
    bool vis[MAXN];
    memset(vis, false, sizeof(vis));
    cntb = 0;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 0; i < chosen.size(); i++)
    {
        vis[chosen[i].bh] = true;
        uni(chosen[i].from, chosen[i].to);
        ++cntk, ++cntb;
    }
    sort(b + 1, b + m + 1, cmp2);
    for (int i = 1; i <= m; i++)
    {
        if (vis[b[i].bh] || (cntk >= k && (!b[i].cost)))
            continue;
        if (find(b[i].from) != find(b[i].to))
        {
            ++cntb;
            uni(b[i].from, b[i].to);
            chosen.push_back(b[i]);
            if (!b[i].cost)
                ++cntk;
        }
        if (cntb >= n - 1)
            break;
    }
    int cntf = 0;
    for (int i = 1; i <= n; i++)
        if (fa[i] == i)
            ++cntf;
    if (cntf > 1 || cntk != k || cntb != n - 1)
        puts("no solution");
    else
        for (int i = 0; i < chosen.size(); i++)
            printf("%d %d %d\n", chosen[i].from, chosen[i].to, chosen[i].cost);
}
int main(int argc, char const *argv[])
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &b[i].from, &b[i].to, &b[i].cost), b[i].bh = i;
    solve();
    return 0;
}

APIO2010巡逻

想到了$k = 1$的时候是找直径, 然后加在两头…

所以$k = 2$的情况就是把那个环去掉然后再找最长链(注意不是直径)…Emmmmm有趣…

所以这么把第一个环去掉呢, 考虑对答案的贡献: ans = ((n - 1) << 1) - length + 1 (在最长链上不用走过去再走回来了, 然后要多经过新加的那一条边) 这是$k = 1$的情况, 那么我们在做第二个环的时候, 把第一个环的边的边权全部赋成$-1$, 这样再减去的时候就不会对答案产生影响(即一条边减了两次)了

还有要注意的一个地方是…我写了找树的直径, 然后一直70不明觉厉…去某谷交发现有三个样例, 然后第二个就过不了…发现不能用找直径的方法做…

反例

大概找第一个环完了就是这个样子, 结果再找直径, 他不会找$6 \to 8$, 而是找了$1 \to 1$, 然后你就凉了, 这个按照高大上的舒老师说的, 要写最长链DP…

Orz

然后最长链抄的hzwer爷爷的…

注意几个问题:

  • 记得初始化(尤其maxz)
  • 在记录第二长的边的时候, 不是赋成他子节点的第二长的边的编号, 而是子节点最长的边的编号…(见line53)
/**************************************************************
    Problem: 1912
    User: Cansult
    Language: C++
    Result: Accepted
    Time:1492 ms
    Memory:8768 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (100000 + 5)
#define INF (0x7fffffff)
#define rev(i) ((((i) - 1) ^ 1) + 1)
#define pii pair<int, int>
using namespace std;
struct dre
{ 
    int s, t, cost;
    dre() {}
    dre(int dqs, int dqt, int dqc): s(dqs), t(dqt), cost(dqc) {}
};
struct node
{
    int max1, max2, max1wz, max2wz, fa;
}ta[MAXN];
struct edg
{
    int from, to, next, cost;
}b[MAXN << 1];
int g[MAXN], cntb, n, k, pre[MAXN], dis[MAXN], maxz = -INF, maxs, maxt, maxr;
int dfs(int dq)
{
    ta[dq].max1wz = ta[dq].max2wz = dq, ta[dq].max1 = ta[dq].max2 = 0;
    for (int i = g[dq]; i; i = b[i].next)
        if (ta[dq].fa != b[i].to)
        {
            pre[b[i].to] = i;
            ta[b[i].to].fa = dq;
            int dqc = b[i].cost + dfs(b[i].to);
            if (dqc > ta[dq].max1)
            {
                ta[dq].max2 = ta[dq].max1, ta[dq].max2wz = ta[dq].max1wz;
                ta[dq].max1 = dqc;
                ta[dq].max1wz = ta[b[i].to].max1wz;
            }
            else if (dqc > ta[dq].max2)
            {
                ta[dq].max2 = dqc;
                ta[dq].max2wz = ta[b[i].to].max1wz; // 注意这个地方可不是赋成ta[b[i].to].max2wz...
            }
        }
    if (ta[dq].max2 + ta[dq].max1 >= maxz)
    {
        maxs = ta[dq].max1wz;
        maxt = ta[dq].max2wz;
        maxr = dq;
        maxz = ta[dq].max2 + ta[dq].max1;
    }
    return ta[dq].max1;
}
int solve()
{
    int re = ((n - 1) << 1);
    if (!k)
        return re;
    ta[1].fa = 1;
    dfs(1);
    int fir = maxz;
    if (k == 1)
        return (re - maxz + 1);
    for (int i = maxs; i != maxr; i = b[pre[i]].from)
        b[pre[i]].cost = b[rev(pre[i])].cost = -1;
    for (int i = maxt; i != maxr; i = b[pre[i]].from)
        b[pre[i]].cost = b[rev(pre[i])].cost = -1;
    for (int i = 1; i <= n; i++)
        ta[i].max1 = ta[i].max2 = 0, ta[i].max1wz = ta[i].max2wz = i;
    maxz = -INF;
    dfs(1);
    return (re - maxz + 1 - fir + 1);
}
void adn(int from, int to, int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1, srx, sry; i < n; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, sry, 1), adn(sry, srx, 1);
    }
    printf("%d\n", solve());
    return 0;
}

未完待续…

By 沙茶 Cansult