前端网站模板,安新seo优化排名网站,海南明确2023年封岛,外贸网站优化推广题意#xff1a;给一张无向图#xff0c;判断能否分成两个生成森林。 n≤2103,m≤4103n\leq 2\times 10^3,m\leq 4\times 10^3n≤2103,m≤4103
题目中这样的图称为“丛林”#xff0c;下面以此来简称。
结论 一张图是丛林的充要条件是它的每一个子图 G(∣V∣,∣E∣)G(|V|,…题意给一张无向图判断能否分成两个生成森林。
n≤2×103,m≤4×103n\leq 2\times 10^3,m\leq 4\times 10^3n≤2×103,m≤4×103
题目中这样的图称为“丛林”下面以此来简称。
结论 一张图是丛林的充要条件是它的每一个子图 G(∣V∣,∣E∣)G(|V|,|E|)G(∣V∣,∣E∣) 有 ∣E∣≤2∣V∣−2|E|\leq 2|V|-2∣E∣≤2∣V∣−2
必要性显然。
充分性考虑归纳法当 ∣V∣1|V|1∣V∣1 时显然成立∣V∣1|V|1∣V∣1 假设结点数小于 ∣V∣|V|∣V∣ 的满足条件的图都是丛林。
引理1 定义满图为满足 ∣E∣2∣V∣−2|E|2|V|-2∣E∣2∣V∣−2 的图对于当前图的两个交非空的子图 G1(V1,E1),G2(V2,E2)G_1(V_1,E_1),G_2(V_2,E_2)G1(V1,E1),G2(V2,E2)它们的并也是满图。
证明 设它们的交为 G3(V3,E3)G_3(V_3,E_3)G3(V3,E3)并为 G(V,E)G(V,E)G(V,E)。由假设知 ∣E1∣2∣V1∣−2,∣E2∣2∣V2∣−2,∣E3∣≤2∣V3∣−2|E_1|2|V_1|-2,|E_2|2|V_2|-2,|E_3|\leq 2|V_3|-2∣E1∣2∣V1∣−2,∣E2∣2∣V2∣−2,∣E3∣≤2∣V3∣−2所以 ∣E∣≥2∣V∣−2|E|\geq 2|V|-2∣E∣≥2∣V∣−2。又因为 ∣E∣≤2∣V∣−2|E|\leq 2|V|-2∣E∣≤2∣V∣−2所以 ∣E∣2∣V∣−2|E|2|V|-2∣E∣2∣V∣−2。得证。
引理2 一个丛林最小的点度数小于 444。
证明 显然。
对于一张满足右边的条件的图它的每一个真子图都是丛林。我们考虑它的一个最小的点的度数如果是 0,1,20,1,20,1,2就把这些边连到外面对应个数的生成森林上得到整张图是丛林。下面讨论度数为 333 的情况。
引理3 当度数为 333 时设相邻的三个点为 a,b,ca,b,ca,b,c删掉这个点 uuu 及这三条边后的图为 GGG那么一定存在 {x,y}⊆{a,b,c}\{x,y\}\subseteq \{a,b,c\}{x,y}⊆{a,b,c} 使得 GGG 中不存在一个满子图包含 x,yx,yx,y。
证明 假设 a,b,ca,b,ca,b,c 两两都被一个满子图包含把这三个满子图合并起来由引理 1合并后的图 FFF 也是满子图即 ∣E(F)∣2∣V(F)∣−2|E(F)|2|V(F)|-2∣E(F)∣2∣V(F)∣−2。我们加入 uuu 和这三条边就得到了一张 ∣E∣2∣V∣−1|E|2|V|-1∣E∣2∣V∣−1 的图它是原图的子图矛盾得证。
我们在 G1G_1G1 中加入一条边 (x,y)(x,y)(x,y)因为不存在包含 (x,y)(x,y)(x,y) 的满图所以加入后 G1G_1G1 仍然是丛林。考虑这棵丛林的两棵生成树在包含 (x,y)(x,y)(x,y) 的树上断掉这条边然后 uuu 分别通过 x,yx,yx,y 连接两个连通分量剩下一个直接连就构造了两棵原图的生产树原命题得证。 现在我们要判断是否对于每一个子图都有
∣E∣≤2∣V∣−2|E|\leq 2|V|-2∣E∣≤2∣V∣−2
∣E∣−2∣V∣≤−2|E|-2|V|\leq -2∣E∣−2∣V∣≤−2
就是最大权闭合子图对于每条边建一个点从 SSS 连边权为 111 的边向两个端点连 ∞\infin∞ 的边每个点到 TTT 连边权为 222 的边跑最小割即可。
设最小割为 ccc,边数为 mmm我们需要判断是否
m−c≤−2m-c\leq -2m−c≤−2
然后你会发现至少有一个大小为 mmm 的割所以会永远输出 No。
冷静分析这样的原因是空图的存在。所以我们要枚举一个点强制选也就是断掉对应的边最后最小割 222当 c−2mc-2mc−2m 时输出 No。
然后要跑 nnn 次完整的 dinic会 T。注意到每次流量改变是常数所以在断掉 (u,v)(u,v)(u,v) 时从 uuu 到 SSS 流 c(u,v)c(u,v)c(u,v) 的流量来模拟退流然后物理断掉这条边。再从 SSS 到 TTT 跑 dinic因为是在几乎已经增广完的残余网络上跑的所以很快。
#include iostream
#include cstdio
#include cstring
#include cctype
#include queue
#define MAXN 6005
#define MAXM 40005
using namespace std;
const int INF0x7fffffff;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
struct edge{int u,v,c;}e[MAXM];
int head[MAXN],cur[MAXN],nxt[MAXM],cnt1;
inline void insert(int u,int v,int c){e[cnt](edge){u,v,c};nxt[cnt]head[u];head[u]cnt;}
inline void addnode(int u,int v,int c){insert(u,v,c),insert(v,u,0);}
int dis[MAXN];
bool bfs(int S,int T)
{queueint q;q.push(T);memset(dis,-1,sizeof(dis));dis[T]0;while (!q.empty()){int uq.front();q.pop();for (int ihead[u];i;inxt[i])if (e[i^1].cdis[e[i].v]-1){dis[e[i].v]dis[u]1;q.push(e[i].v);if (e[i].vS) return true;}}return false;
}
int dfs(int u,int f,int T)
{if (uT||!f) return f;int used0;for (int icur[u];i;inxt[i])if (e[i].cdis[u]dis[e[i].v]1){int wdfs(e[i].v,min(e[i].c,f),T);e[i].c-w,e[i^1].cw;f-w,usedw;if (!f) break;}if (!used) dis[u]-1;return used;
}
inline int dinic(int S,int T,int fINF)
{int ans0;while (fansbfs(S,T))memcpy(cur,head,sizeof(head)),ansdfs(S,f-ans,T);return ans;
}
int pos[MAXN];
int solve()
{memset(head,0,sizeof(head));memset(nxt,0,sizeof(nxt));cnt1;int n,m;nread(),mread();int Snm1,TS1;for (int i1;im;i){addnode(ni,read(),INF);addnode(ni,read(),INF);addnode(S,ni,1);}for (int i1;in;i) addnode(i,T,2),pos[i]cnt;int ansdinic(S,T);for (int i1;in;i){int fe[pos[i]].c;e[pos[i]].ce[pos[i]^1].c0;if (f) ans-dinic(i,S,f);if (i1) e[pos[i-1]^1].c2;ansdinic(S,T);if (ansm) return puts(No),0;}puts(Yes);return 0;
}
int main()
{for (int Tread();T;T--) solve();return 0;
}
