记录一些散题 / 价值不大但还是想记下来的题目 / 没正八经写博客的题目
8.24
Luogu P1508 沙雕题数字三角形的二维升级版，但是注意阅读理解，李大水牛从桌子最后一行下侧开始吃，而本题是自下而上，其实按自上而下做也行，只不过最后的答案变成了三者取一最值。（面前、左上、右上）其他与数字三角形无异。
#include<cstdio>
#include<algorithm> using namespace std; int n,m;
int f[][]; int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&f[i][j]);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
f[i][j]+=max(f[i-][j-],max(f[i-][j],f[i-][j+]));
int qwq=(m+)>>;
printf("%d",max(f[n][qwq],max(f[n][qwq-],f[n][qwq+])));
return ;
}
8.23
Luogu P1550 最小生成树。（这题记得第一次月考完和Chemist在机房想一起刷点贪心，我抽到了这个题，两人一起做，后来才发现是MIT，但是我没做，大神写了qwq我四个月以后才写qwq）.鉴于每个农庄自己凿井的情形，我们可以再构造一个源点，让所有自己凿井的情况与源点连边。然后就是裸的MIT了。但是注意无向边开两倍，还因为这个制杖错误没能1A，热了三个点orz。。。
Luogu P1993 差分约束系统。判断不等式组是否有解，直接建图判是否有负环。实践了一下可爱lyc的差分约束系统理论，但是漏洞百出。果然实践出针织qwq。
几个注意地方：1 不等式要化对
2 最后把所有的点和0连0权边，而不是仅把输入中涉及的点连
3 据说本题会卡bfs-spfa判负环，抄题解学习了一下dfs版本的spfa判负环，可以留当板子用。
4 spfa中dis[0]=0（这还需要说嘛）
5 head数组初值为-1，因为有编号为0的点存在。（没有亲测如果不赋会怎样，题解中不赋貌似也能过，可能是数据较弱的缘故）。
#include<cstdio>
#include<algorithm>
#include<cstring> using namespace std; int n,m,tot;
int head[],vis[],dis[];
struct node{
int next,to,val;
}edge[]; void add(int x,int y,int z)
{
edge[++tot].val=z;
edge[tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
} bool spfa(int u)
{
vis[u]=;
for(int i=head[u];i!=-;i=edge[i].next)
if(dis[edge[i].to]>dis[u]+edge[i].val)
{
dis[edge[i].to]=dis[u]+edge[i].val;
if(vis[edge[i].to]) return ;
if(!spfa(edge[i].to)) return ;
}
vis[u]=;
return ;
} int main()
{
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
memset(dis,,sizeof(dis));
for(int i=;i<=m;i++)
{
int opt=,a=,b=,c=;
scanf("%d",&opt);
if(opt==)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,-c);
}
else if(opt==)
{
scanf("%d%d%d",&a,&b,&c);
add(b,a,c);
}
else if(opt==)
{
scanf("%d%d",&a,&b);
add(a,b,);
add(b,a,);
}
}
for(int i=;i<=n;i++) add(,i,);
dis[]=;
if(spfa()) printf("Yes");
else printf("No");
return ;
}
留几个待填坑吧：
瓶颈树
集合
控制公司
无向图tarjan
奶牛家谱
派对灯