wxwoo's blog

评论系统

链接请填写OJ账户(luogu优先),选填
邮箱用于验证和回复通知,必须填写
无法匿名评论
头像请用你的邮箱,到gravatar设置
由于评论管理系统尚未部署完成(其实就是咕咕咕了),不一定会发送邮件

原题目链接

先无视租机器,明显的最大权闭合子图

最大权闭合子图:

给定一个有向图,点有点权,选择一个子图,满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

我们将机器和任务都看成一个点

如果这题没有租机器,这题的建边方式就应该是这样:

  1. 源点向订单连流量为利润的边

  2. 机器向汇点连流量为购买价格的边

  3. 每个订单向需要的机器连流量为inf的边

可以发现,源点连的边都是订单的利润,汇点连的边都是机器的成本,只有机器和订单之间的边是$inf$

对于每个订单需要的相同机器,租用的价格也不一样

所以我们考虑把$inf$换成租机器的费用

从正确性的角度考虑,跑最大流(最小割)是计算最优方案下的成本,若总租借费用低于购买机器费用,表示购买费用的那条边就不会满流,防止购买机器反而增加成本;反之表示购买费用的那条边就会满流,限制住成本因多次租用同一机器而增加

最终建边方式如下:

  1. 源点向订单连流量为利润的边

  2. 机器向汇点连流量为购买价格的边

  3. 每个订单向需要的机器连流量为租用费用的边

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x)
{
int ch=getchar();
T f=1;
x=0;
while(!('0'<=ch&&ch<='9'))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-48;
ch=getchar();
}
x*=f;
}
const int inf=1e9,N=3e5+1;
struct edge
{
int from,to,nxt,cap,flow;
}e[N*20];
int cnt,n,m,sour,sink,head[N],ans,q[N],l[N],p[N];
inline void add(const int &u,const int &v,const int &f)
{
e[++cnt]=(edge){u,v,head[u],f,0};
head[u]=cnt;
e[++cnt]=(edge){v,u,head[v],0,0};
head[v]=cnt;
}
inline bool find()
{
memset(l,0,sizeof(l));
int h=1,t=1;
q[1]=sour;
l[sour]=1;
while(h<=t)
{
int x=q[h++];
for(int i=head[x];i;i=e[i].nxt)
{
if(!l[e[i].to]&&e[i].cap>e[i].flow)
{
q[++t]=e[i].to;
l[e[i].to]=l[x]+1;
if(e[i].to==sink)
return 1;
}
}
}
return 0;
}
int dfs(const int &x,const int &now)
{
if(x==sink||!now)
return now;
int t=now,detla;
for(int i=head[x];i;i=e[i].nxt)
{
if(e[i].cap>e[i].flow&&l[e[i].to]==l[x]+1)
{
detla=dfs(e[i].to,min(t,e[i].cap-e[i].flow));
if(!detla)
l[e[i].to]=0;
e[i].flow+=detla;
e[((i-1)^1)+1].flow-=detla;
t-=detla;
if(t==0)
break;
}
}
return now-t;
}
inline void dinic()
{
while(find())
ans+=dfs(sour,inf);
}
int main()
{
read(n);
read(m);
sour=0;
sink=n+m+1;
int u,v,t,r,tot=0;
for(int i=1;i<=n;++i)
{
read(v);
read(t);
add(sour,i,v);
for(int j=1;j<=t;++j)
{
read(u);
read(r);
add(i,u+n,r);
}
tot+=v;
}
for(int i=1;i<=m;++i)
{
read(v);
add(i+n,sink,v);
}
dinic();
printf("%d",tot-ans);
return 0;
}

原题目链接

明显的最大权闭合子图

最大权闭合子图:

给定一个有向图,点有点权,选择一个子图,满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

经典的网络流问题,具体使用最小割求解

我们将顾客和通讯站都看成一个点,然后如下建边:

  1. 源点向顾客连流量为利润的边

  2. 通讯站向汇点连流量为成本的边

  3. 每个顾客向需要的通讯站连流量为inf的边

原题目链接

树上链最值查询

做法很多,LCT,树上倍增,树剖都可以

但由于LCT常数过大,树上倍增比树剖常数大,这里使用树链剖分

边权转点权是树剖常用套路,将边权转成深度较大的点的点权,查询时注意避开两点的LCA的权值

由于不带修改,树剖后用ST表维护,时间复杂度$\mathcal{O}(n\log n)$,比用线段树维护$\mathcal{O}(n\log ^2n)$还少一个log

在使用hexo博客和material-x等博客主题时,难免会遇到mathjax数学公式渲染失败或者与markdown渲染冲突的问题。

xaoxuu给出了解决方案,只需在_config.yml里加入mathjax: true即可解决,可以解决大量的mathjax公式渲染,但仍有部分复杂的公式渲染出现问题。

我在这里给出一种解决方案。

注:部分资料来自互联网


载入天数...载入时分秒...


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。