图论的各种奇技淫巧

就是想复习一下图论…..

2019.4.7高中部集训

课程表

上午
  • 讲评考试、$Tarjan$
下午
  • 依然$Tarjan$

2019.4.6高中部集训

课程表

上午

  • 考试$QAQ$

下午

  • 考试$QAQ$

晚上

  • 讲评考试$QAQ$(其实在听讲座)

  • 最近在刷洛谷试炼场的时候,做到了P2330这道题,一看到有个生成树的条件是要让最长的边最短,感觉很熟悉,记得最小生成树就一定满足这一性质,但是还是不会证。
  • 于是我就百度了一下$QAQ$

洛谷1194 买礼物

  • 图论的最后这道题竟然这么简单,只有建图的问题,其他就是非常基础最小生成树了。
  • 优惠就是图中的一条边,不要建边两次,最小生成树我用的是$Kruskal$。
  • Code:
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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{
int u,v,w;
}e[250005];
int A,B,cnt,tot=1,ans,f[505];
bool cmp(node x,node y){
return x.w<y.w;
}
int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void Update(int a,int b){
int x=find(a);
int y=find(b);
if(x!=y) f[x]=y;
return;
}
void addEdge(int a,int b,int c){
cnt++;
e[cnt].u=a;
e[cnt].v=b;
e[cnt].w=c;
return;
}
void kruskal(){
int i=1;
while (i<=cnt&&tot<=B){
if (find(e[i].u)!=find(e[i].v)){
tot++;
ans+=e[i].w;
Update(e[i].u,e[i].v);
}
i++;
}
return;
}
int main(){
scanf("%d%d",&A,&B);
for(int i=1;i<=B;i++)
for(int j=1;j<=B;j++){
int w;
scanf("%d",&w);
if(i<j&&w!=0) addEdge(i,j,w);//0的情况要特判!
}
for(int i=1;i<=B;i++) addEdge(0,i,A);
for(int i=0;i<=B;i++) f[i]=i;
sort(e+1,e+cnt+1,cmp);
kruskal();
printf("%d\n",ans);
return 0;
}

高中部寒假集训Day2

Day2:

先放课程表:

2019.1.24

上午
  • 讲解订正$Day1$晚上考试的题目。
下午
  • 图论:最小生成树
晚上
  • 考试:贪心

考试

  • 时空限制:1000ms/512MB
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×