树形DP

CodeForces 19E Fairy

Posted on

一道二分图性质的应用 + 树形DP ?

看博客里都说是树形DP,但我觉得应该是树上前缀和更加合适一些

题意:
给你一个图,让你删除一条边,使得剩下的图是二分图。
输出可删边数并顺序输出边的序号。

思路:
首先你必须知道判定二分图的充要条件 —— 不存在奇环。
如果只是让你判定二分图的话,倒是随便搜一遍就可以解决的问题。
但是这里必须让你删掉一条边……

写不来……感觉不好写,最后无奈去看题解了……

先整理一下判断思路:

  1. 如果不存在奇环,那么原图本来就是一张二分图,每一条边都满足条件
  2. 覆盖了所有的奇环,并且不能覆盖偶环的所有边

为什么同时不能覆盖偶环,这个我还真没想到,但是在纸上画一画就是很显然的了,同时覆盖奇环和偶环的边删去后,两个环会变成一个新的环,偶数+奇数 还是奇数。所以不能覆盖偶环。

因此得出如下具体实现,随便生成一棵生成树,用树上前缀和计算出每一条树边覆盖的奇环数和偶环数。
如果奇环数量大于 1 ,那么非树边必定不可能是满足条件的,因为非树边最多只能覆盖一个环,两个及以上就是重边了。因此非树边只有在奇环数量等于 1 的时候才需要我们去考虑,如果该非树边覆盖了奇环,则删之。
而对于树边,判断其覆盖奇环数和偶环树是否满足条件即可。

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e6 + 5;
const int maxm = 2e6 + 5;
int n, m, top, cnt;

pii edges[maxm];
int head[maxn];
int idx;

int odd[maxn], even[maxn];
int dep[maxn], edge_type[maxm];
bool vis[maxn];

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

void dfs(int u, int e)
{
    vis[u] = true;
    dep[u] = ++top;
    int v;
    for (int id = head[u]; ~id; id = edges[id].second) {
        if (edge_type[id] == -1)
            continue;
        v = edges[id].first;
        if (!vis[v]) {
            edge_type[id] = edge_type[id ^ 1] = -1;
            dfs(v, id >> 1);
            odd[e] += odd[id >> 1];
            even[e] += even[id >> 1];
        } else {
            if (edge_type[id] == 1)
                odd[e]--;
            else if (edge_type[id] == 2)
                even[e]--;
            else {
                if ((dep[u] - dep[v]) & 1)
                    even[e]++, edge_type[id] = edge_type[id ^ 1] = 2;
                else
                    odd[e]++, edge_type[id] = edge_type[id ^ 1] = 1, cnt++;
            }
        }
    }
    top--;
}

int ans[maxn], anum;

int main()
{
    int u, v;
    scanf("%d %d", &n, &m);
    fill(head, head + n + 1, -1);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, 0);
    if (cnt == 0) {
        printf("%d\n", m);
        for (int i = 1; i <= m; i++)
            printf("%d ", i);
    } else {
        for (int i = 0; i < m; i++)
            if (odd[i] == cnt && even[i] == 0)
                ans[anum++] = i;
            else if (cnt == 1 && edge_type[i << 1] == 1)
                ans[anum++] = i;
        printf("%d\n", anum);
        for (int i = 0; i < anum; i++)
            printf("%d ", ans[i] + 1);
    }
    return 0;
}
书评影评

《刀剑神域:序列之争》个人简评

Posted on

刚看完,特想大喊一声:“爽!”

真的,光是100层BOSS战对我来说来回看个10遍还是很过瘾!!
等等,100层BOSS说好不是茅场么??
不管是那种应对庞然大物,咬牙切齿挥舞着两把剑,还是在刀刃下切割的肉体,这种激烈的战斗场面真的只有 虚拟的 二次元中才会拥有!!当然整部动漫的战斗场面更是在BOSS战中达到了巅峰!!

抛开战斗场面不说,情怀分就可以达到满分,两季TV出现的角色都会在这里以各种形式出现,因为要夺取SAO幸存者的记忆,虚拟现实的玩家锐减,角色的出现显得比较自然,在最后BOSS战中又是还原了各自最具有特色的装备,在情怀上也是上升到了极致。

另外在剧场版再次强调了亚丝娜正宫的位置,狗粮发的也是诚意满满,在洗面奶的那个场景亚丝娜居然没有一点脸红,观众席都是一片哗然……
话说字幕组对亚丝娜的名字翻译总是在亚丝娜和明日香之间来回随机跳跃是几个意思呀……强迫症表示受不了……

因为有yuna这样的唱歌辅助角色存在,整部影片在音乐上也是无可挑剔的,顺便说一声影片结束后别急着离开,最后放的音乐也是超好听的!!!

至于剧情方面嘛,我放到最后讲,也因为它只能在及格线吧,以与VR相对的AR为技术基础,最近比较风靡的排位系统为背景。然而桐人一开始对AR的不喜 缺乏锻炼的宅男?? ,还被一个SAO时期的一个比较懦弱的玩家看不起了 结果居然是个挂B,特么开挂还这么吊 ,但是亚丝娜在打BOSS战被夺取SAO的记忆,失去了很多跟桐人珍贵的回忆,被逼地躲在房间默默痛哭,老婆都被欺负了,桐人当然不能忍,于是开始认真了起来,自然而然就开始装逼了但真的很帅有木有??。不过最后打倒100层BOSS后切演唱会的BOSS真的有点敷衍了,全都一刀秒??
另一方面在排位系统上好像高排位的优势并没有很好的体现,除了一些现实的优惠以外,就只说了rank 1 的不死属性,最开始看到rank 1没有显示,我就知道结局了
不过TV动漫的剧场版本来就是以情怀更显得保守一些,这一点我想是为大众所接受的,反正这30块我倒是花的很开心。