复杂度分析全部摘自题解
T1
sb优化暴力
暴力20～40pts，我只拿了20pts。
正解：
bitset 优化暴力，但是会MLE。
再次考虑如何优化，我们统计一下每个点的入度，每次遍历到这个点的时候，将其入度-1，发现当其入度减到0的时候，对答案就没有了贡献，而它还在bitset中，可以给这种点扔掉 好像是叫垃圾回收 复杂度 \(O(\frac{n(n+m)}{w})\)
也可以类似分块来做，就是分成两部分来统计答案。
Code
#include<bitset>
#include<cstdio>
#define N 60010
#define M 100010
#define re register
namespace OMA
{
int n,m,ans;
struct Graph
{
int next;
int to;
}edge[M];
bool vis[N];
int id[N],in[N];
int sta[N],top;
int cnt=1,head[N];
std::bitset<N>bit[N/3];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘)w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); }
return s*w;
}
inline void add(int u,int v)
{
edge[++cnt].next = head[u];
edge[cnt].to = v;
head[u] = cnt;
}
inline int NEW()
{ return top?sta[top--]:++cnt; }
inline void DEL(int u)
{ ans += bit[sta[++top] = id[u]].count(),bit[id[u]].reset(); }
inline void dfs(int u)
{
vis[u] = true;
if(!id[u])
{ id[u] = NEW(); }
for(re int i=head[u]; i; i=edge[i].next)
{
int v = edge[i].to;
bit[id[u]][v] = 1;
in[v]--;
if(vis[v])
{ bit[id[u]] |= bit[id[v]]; if(!in[v]){ DEL(v); } continue ; }
dfs(v);
bit[id[u]] |= bit[id[v]];
if(!in[v])
{ DEL(v); }
}
}
signed main()
{
n = read(),m = read();
for(re int i=1,u,v; i<=m; i++)
{ u = read(),v = read(),add(u,v); in[v]++; }
cnt = 0;
for(re int i=1; i<=n; i++)
{ if(!vis[i]){ dfs(i); if(!in[i]){ DEL(i); } } }
printf("%d\n",ans-m);
return 0;
}
}
signed main()
{ return OMA::main(); }
T2
考场骗分结果写挂了，10pts都没骗着，好吧。其实是我把电阻跟节点搞混了所以为什么变量名是对的
想到了平衡树查询后继，但发现维护的信息太多，不太好搞，就放弃了 我都码完了板子才意识到这个问题
正解：
考虑贪心，首先将电阻和节点都按 \(l\) 排序，然后考虑给节点按电阻，对于当前这个节点，有多个 \(l\) 符合条件的电阻，那么肯定是要去选最接近当前节点的 \(r\) 的且比它大的电阻。直接写70pts，复杂度\(O(nm)\) ，会TLE。
考虑如何优化，可以用一个 \(set\)来维护符合条件的电阻。将当前 \(l\) 符合条件的电阻都插里边，然后 \(lower\;bound\) 查找符合贪心策略的电阻，\(set\)是结构体类型的，所以可以重载\(<\) 来查找，一开始的按\(l\) 排序写个比较函数就好。复杂度 \(O((n+m)\log m+n\log n)\)
Code
#include<set>
#include<cstdio>
#include<algorithm>
#define MAX 50010
#define re register
#define LL long long
namespace OMA
{
int root;
struct node
{
int l,r,k;
inline friend bool operator <(const node &a,const node &b)
{ return a.r<b.r; }
}p[MAX],r[MAX],tmp;
inline bool cmp(const node &a,const node &b)
{ return a.l<b.l; }
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘)w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); }
return s*w;
}
int t,n,m;
std::multiset<node>s;
std::multiset<node>::iterator it;
signed main()
{
t = read();
while(t--)
{
bool flag = true;
n = read(),m = read();
for(re int i=1; i<=n; i++)
{ p[i] = (node){read(),read(),read()}; }
for(re int i=1; i<=m; i++)
{ r[i] = (node){read(),read(),read()}; }
int pos = 1;
std::sort(p+1,p+1+n,cmp),std::sort(r+1,r+1+m,cmp);
for(re int i=1; i<=n; i++)
{
while(pos<=m&&r[pos].l<=p[i].l)
{ s.insert(r[pos]); pos++; }
while((it = s.lower_bound(p[i]))!=s.end())
{
tmp = *it;
s.erase(it);
if(tmp.k>=p[i].k)
{ tmp.k -= p[i].k,p[i].k = 0; if(tmp.k>0){ s.insert(tmp); } break ; }
else
{ p[i].k -= tmp.k; }
}
if(p[i].k!=0)
{ flag = false; break ; }
}
if(!flag)
{ printf("No\n"); }
else
{ printf("Yes\n"); }
s.clear();
}
return 0;
}
}
signed main()
{ return OMA::main(); }
T3
考场啥也没想出来，tarjan割边也忘了，直接暴毕。
60pts：
\(n=m\) ，是个环套树，所以树边肯定在最小生成树中，答案为-1，环边如果想在所有最小生成树中，只有当其权值小于其他环边的最大值，所以某条环边的答案即为其余环边的最大值-1。复杂度\(O(n)\) 。
\(w=1\)，边权都是1,所以判断这条边是不是割边就好了，是，肯定在所有最小生成树中，不在的话，只有权值为0才能在所有最小生成树中。复杂度也是\(O(n)\) 。
60pts
#include<cstdio>
#include<algorithm>
#define MAX 200100
#define re register
int n,m,a;
long long ans[MAX];
bool vis[MAX],cut[MAX];
struct Graph
{
int u,v,w,id;
inline friend bool operator <(const Graph &a,const Graph &b)
{ return a.w<b.w; }
}edge[MAX];
struct graph
{
int next;
int to;
}Edge[MAX<<1];
int cnt=1,head[MAX];
namespace MST
{
int dsu[MAX];
inline int find(int x)
{ return x!=dsu[x]?dsu[x] = find(dsu[x]):dsu[x]; }
inline bool kruskal(int k)
{
int r1,r2;
for(re int i=1; i<=n; i++)
{ dsu[i] = i; }
for(re int i=1; i<=m; i++)
{
if(i!=k)
{
r1 = find(edge[i].u),r2 = find(edge[i].v);
if(r1!=r2)
{
dsu[r2] = r1;
if(find(edge[k].u)==find(edge[k].v))
{ ans[edge[k].id] = edge[i].w-1; return 1; }
}
}
}
return 0;
}
}using namespace MST;
namespace Tarjan
{
int dfn[MAX],low[MAX],num;
inline int min(int a,int b)
{ return a<b?a:b; }
inline void tarjan(int u,int nt)
{
dfn[u] = low[u] = ++num;
for(re int i=head[u]; i; i=Edge[i].next)
{
if(vis[i])
{ continue ; }
vis[i] = vis[i^1] = 1;
int v = Edge[i].to;
if(!dfn[v])
{
tarjan(v,i);
low[u] = min(low[u],low[v]);
if(low[v]>dfn[u])
{ cut[i>>1] = 1; }
}
else if(i!=(nt^1))
{ low[u] = min(low[u],dfn[v]); }
}
}
}using namespace Tarjan;
namespace OMA
{
inline void add(int u,int v)
{
Edge[++cnt].next = head[u];
Edge[cnt].to = v;
head[u] = cnt;
}
inline void dfs(int u)
{
for(re int i=head[u]; i; i=Edge[i].next)
{
if(!vis[i])
{
vis[i] = vis[i^1] = 1;
int v = Edge[i].to; dfs(v);
}
}
}
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘)w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); }
return s*w;
}
signed main()
{
n = read(),m = read(),a = read();
for(re int i=1; i<=m; i++)
{
int u = read(),v = read(),w = read();
add(u,v),add(v,u),edge[i] = (Graph){u,v,w,i};
}
if(!a)
{
dfs(1),std::sort(edge+1,edge+1+m);
for(re int i=1; i<=m; i++)
{
if(!vis[edge[i].id<<1])
{ ans[edge[i].id] = 0; continue ; }
if(!kruskal(i))
{ ans[edge[i].id] = -1; }
}
for(re int i=1; i<=m; i++)
{ printf("%lld ",ans[i]); }
}
else
{
tarjan(1,0);
for(re int i=1; i<=m; i++)
{ printf("%d ",cut[i]?-1:0); }
}
return 0;
}
}
signed main()
{ return OMA::main(); }
100pts：
没改出来，所以...咕了