当前位置: 首页 > news >正文

学霸的期末 解题报告

简要题意

给定 \(n\) 个点 \(m\) 条边的有向图,在不改变图的连通性的前提下,删除任意条边后,最少可以保留多少条边;和任意加边后,最多可以包含多少条边。

数据范围:\(nm \le 5 \times 10 ^7,n \le 10^3,m\le 10^5\)

分析

先做第二问,等价于有多少有序点对 \((u,v)\) 满足 \(u\) 可达 \(v\),直接搜索即可。

再看第一问,我们考虑先缩点,然后在一个非单点的强连通分量中,我们可以只保留强连通分量大小条边;然后对于缩点后的新图,可以在 \(O(n^2)\) 的时间内预处理每一个点可以到达的点集,和可以到达一个点的点集,我们枚举每一条边 \((u,v)\),求 \(u\) 可到点集和可到 \(v\) 点集的交集,如果交集为空,那么该边必须保留。用 bitset 优化,时间复杂度为 \(O(\dfrac{nm}{w})\)

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf (1ll<<60)
#define For(i,s,t) for(int i=s;i<=t;++i)
#define Down(i,s,t) for(int i=s;i>=t;--i)
#define ls (i<<1)
#define rs (i<<1|1)
#define bmod(x) ((x)>=p?(x)-p:(x))
#define lowbit(x) ((x)&(-(x)))
#define End {printf("NO\n");exit(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline void ckmx(int &x,int y){x=(x>y)?x:y;}
inline void ckmn(int &x,int y){x=(x<y)?x:y;}
inline void ckmx(ll &x,ll y){x=(x>y)?x:y;}
inline void ckmn(ll &x,ll y){x=(x<y)?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline ll max(ll x,ll y){return x>y?x:y;}
char buf[1<<20],*p1,*p2;
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({\int x = 0, f = 1;\char c = gc();\while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = gc();\while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc();\f * x;\
})
void write(int x){if(x>=10) write(x/10);putchar(x%10+'0');
}
const int N=2050;
int n,m,ans,ans0;
struct Edge{int from,f,to;}e[N<<1];
int num,h[N];
void add(int f,int t){e[++num].from=h[f],e[num].f=f,e[num].to=t,h[f]=num;}
int dfn[N],low[N],s[N],tail,col[N],sz[N],dfu,cnt;
bool in[N];
void tarjan(int u){dfn[u]=low[u]=++dfu;s[++tail]=u,in[u]=true;for(int i=h[u];i;i=e[i].from){int v=e[i].to;if(!dfn[v])tarjan(v),ckmn(low[u],low[v]);else if(in[v])ckmn(low[u],dfn[v]);}if(low[u]==dfn[u]){++cnt;while(tail){int v=s[tail];--tail;in[v]=false;col[v]=cnt;++sz[cnt];if(v==u) break;}}
}
struct pair_hash{template <class T1,class T2>size_t operator() (const pair<T1,T2>& p) const{auto hash1=hash<T1>{}(p.first);auto hash2=hash<T2>{}(p.second);return hash1^(hash2<<15);}
};
unordered_set<pii,pair_hash> t;
void build_DAG(){num=0;For(i,1,n) h[i]=0;For(i,1,m){int u=e[i].f,v=e[i].to;if(col[u]==col[v] || t.find(pii(col[u],col[v]))!=t.end()) continue;t.insert(pii(col[u],col[v]));add(col[u],col[v]);}
}
void dfs1(int u){if(in[u]) return;++ans;in[u]=true;for(int i=h[u];i;i=e[i].from)dfs1(e[i].to);
}
bitset<N> to[N],from[N];
void dfs(int u,int st){if(to[st][u]) return;to[st][u]=from[u][st]=1;for(int i=h[u];i;i=e[i].from)dfs(e[i].to,st);
}
int main()
{
#if !ONLINE_JUDGEfreopen("compare.in","r",stdin);freopen("compare.out","w",stdout);
#endif n=read(),m=read();int u,v;For(i,1,m) u=read(),v=read(),add(u,v);For(i,1,n){For(j,1,n) in[j]=false;dfs1(i),--ans;}For(i,1,n)if(!dfn[i])tarjan(i);// For(i,1,n) printf("%d ",col[i]);// putchar('\n');build_DAG();For(i,1,cnt) dfs(i,i);For(i,1,cnt) from[i][i]=to[i][i]=false;For(i,1,cnt) ans0+=(sz[i]>1 ? sz[i] : 0);For(i,1,num){int u=e[i].f,v=e[i].to;// printf("%d %d\n",u,v);if((to[u]&from[v]).count()==0) ++ans0;}printf("%d %d\n",ans0,ans);return 0;
}
http://www.hskmm.com/?act=detail&tid=32221

相关文章:

  • 一种适用于正整数值域的无旋平衡树
  • 2025 年电子散热器厂家 TOP 企业品牌推荐排行榜,电子 / 型材 / 插片 / 电源 / 固态 / 变频器 / 铝合金 / 逆变器散热器 / 散热器铝型材公司推荐
  • 禁用sentinel
  • 静态网站宣言:用IPFS重建开放网络的乐趣
  • 收敛数列的性质
  • Eclipse Mosquitto MQTT 代理中持久性引擎(database.c 概念)的作用分析报告 - 指南
  • FFmpeg 实现视频批量剪辑
  • 2023盘古石 物联网取证部分
  • 2025 年自润滑轴承厂家联系方式推荐,宁波索力特复合材料有限公司专业产品与可靠服务指南
  • MATLAB PSO-PF 融合滤波
  • SaltStack 集群安装指南
  • nginx基本配置详解
  • NCS 3.1.1 蓝牙如何设置 public 地址
  • C# Avalonia 16- Animation- BlurringButtons
  • iOS 26 崩溃日志导出全流程,多工具实践 辅助分析策略
  • 小白也能学会的 rime + 万象拼音 输入法安装教程
  • 别再争了,“Prompt已死”是个伪命题
  • 2025.10.16——1绿
  • 2025年通风气楼厂家最新权威推荐榜:工业厂房自然通风与消防排烟系统专业解决方案精选
  • 2025 年展柜定制厂家最新推荐排行榜:聚焦全链条服务与大规模生产能力的优质品牌精选
  • 了解漏洞管理和补丁管理
  • 于鸿硕项目案例作业03
  • restful接口返回忽略字段 jackon的@JsonIgnore注解应用
  • Windows系统-应用问题全面剖析Ⅱ:德承工控机DC-1300在Windows操作系统下[TPM功能]设置教程 - Johnny
  • 挂在天上放光明,好像一群IDA*
  • 元推理框架,是逻辑产物,也是逻辑功能,佛渡有缘人
  • 2025 年国内铝型材源头厂家最新推荐排行榜:聚焦优质企业核心优势,为下游企业精准采购提供专业参考
  • 基于遗传方法的动态多目标优化算法
  • 【linux内核】内核类型
  • 2025年脱模剂混合机厂家最新推荐排行榜,高效混合机,立式混合机,卧式混合机,化工混合机,脱模剂专用混合设备厂家精选