没想到是网络流
官方题解地址
http://jiry-2.blog.uoj.ac/blog/1115
subtask2告诉我们度数为012的点对答案无影响
subtask3告诉我们原图\(|E| > 2|V| - 2\)时不是丛林的
证明一个结论
若对于原图所有的子图都满足\(|E| \le 2|V| - 2\)则是一个丛林
对子图大小施归纳法
\(n = 1\)是丛林
当\(n \geq 2\)时
设当前图度数最小的节点为\(u\)
仅讨论\(du[u] = 3\)的情况(0, 1, 2同subtask2)
记\(|E| = 2|V| - 2\)的子图为Dark图
Dark 交 Dark 得到的图也是Dark
证明的话考虑总的减去交的 每一部分都是满足的
然后设\(u\)在原图和\(a, b, c\)有边
在原图必不存在包含\(a, b, c\)的Dark子图（反证法）
然后就可以科学的构造\(n\)的时候的丛林了
如果有一个Dark子图包含\(a,b\)不包含\(c\)
那么一颗树选择\(u->a, u->b\)另一棵树选择\(u->c\)
然后就是问是否存在一个非空子图
满足\(|E| > 2|V| - 2\)
相当于点权值为\(-2\)边权值为\(1\)
这是一个最大权闭合子图的模型
但是是非空的
那么就枚举必选哪一个点
把这个点权值设成\(0\)跑网络流就好了
复杂度是\(\mathcal O(nm\sqrt n)\)的
观察到每一次枚举一个点只会改变一条边和他的反向边流量
所以退流就好了
学了一下退流的姿势
比如说要退边\(<u, v>\)的流
只需要\(t->v\)和\(u->s\)分别跑最大流就好了
感性YY一下
可能讲的好乱 看官方题解吧
#include <bits/stdc++.h>
#define rint register int
#define fo(i, n) for(int i = 1; i <= (n); i ++)
#define out(x) cerr << #x << " = " << x << "\n"
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); ++ it)
using namespace std;
// by piano
template<typename tp> inline void read(tp &x) {
x = 0;char c = getchar(); bool f = 0;
for(; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
for(; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
if(f) x = -x;
}
namespace mf {
static const int N = 8888;
static const int M = 23333;
static const int inf = 1e9;
struct E {
int nxt, to, fl;
}e[M << 1];
int d[N], head[N], cur[N], e_cnt = 1;
int n, s, t;
inline void init(int _n, int _s, int _t) {
n = _n; e_cnt = 1;
fill(head, head + n + 1, 0);
}
inline void add(int u, int v, int fl) {
e[++ e_cnt] = (E) {head[u], v, fl}; head[u] = e_cnt;
}
inline void link(int u, int v, int fl) {
add(u, v, fl); add(v, u, 0);
}
inline bool bfs(void) {
queue<int> q;
fill(d, d + n + 1, -1);
d[s] = 0; q.push(s);
while(!q.empty()) {
int u = q.front(); q.pop();
for(rint i = head[u]; i; i = e[i].nxt) if(e[i].fl) {
int v = e[i].to;
if(!~ d[v]) {
d[v] = d[u] + 1, q.push(v);
if(v == t) return true;
}
}
}
return d[t] != -1;
}
inline int dfs(int u, int f) {
if(u == t || !f) return f;
rint used = 0, t;
for(rint &i = cur[u]; i; i = e[i].nxt) if(e[i].fl) {
int v = e[i].to;
if(d[v] != d[u] + 1) continue;
t = dfs(v, min(f - used, e[i].fl));
used += t; e[i].fl -= t; e[i ^ 1].fl += t;
if(used == f) break;
}
if(!used) d[u] = -1;
return used;
}
inline int doit(int _s, int _t, int f) {
int fl = 0; s = _s; t = _t;
while(bfs() && fl < f) {
memcpy(cur, head, sizeof (int) * (n + 2));
fl += dfs(s, f - fl);
}
return fl;
}
}
const int inf = 1e9;
int n, m, s, t;
#define GG return puts("No"), 0;
main(void) {
read(n); read(m);
s = n + m + 1; t = s + 1;
mf::init(t, s, t);
for(rint i = 1; i <= n; i ++) {
mf::link(i, t, 2);
}
for(rint i = 1; i <= m; i ++) {
mf::link(s, i + n, 1);
}
for(rint i = 1; i <= m; i ++) {
int x, y; read(x); read(y);
mf::link(i + n, x, inf);
mf::link(i + n, y, inf);
}
int fl = mf::doit(s, t, inf);
if(m - fl > 0) GG;
for(rint i = 1; i <= n; i ++) {
fl -= mf::doit(i, s, mf::e[i * 2 + 1].fl);
mf::e[i * 2].fl = mf::e[i * 2 + 1].fl = 0;
fl += mf::doit(s, t, inf);
if(m - fl > 0) GG;
mf::e[i * 2].fl = 2;
}
cout << "Yes\n";
}