正文

模拟考试：图论专场

fujudge  fujudge  2022-09-18  411

关键词：

Phone

【问题描述】

由于地震使得连接汶川县城电话线全部损坏，假如你是负责将电话线接到震中汶川县城的负责人，汶川县城周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线，其余的那些由于地震使得电线杆已经倒塌而无法被连接。

第i对电话线杆的两个端点分别为Ai、Bi，它们间的距离为Li (1 <= Li <= 1,000,000)。数据中保证每对（Ai，Bi）最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个县城的电话线全都连到了编号为N的电话线杆上。也就是说，你的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。

电信公司决定支援灾区免费为汶川县城连结K(0<=K<N)对由你指定的电话线杆。对于此外的那些电话线，需要为它们付费，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过K对，那么总支出为0。

请你计算一下，将电话线引到震中汶川县城最少需要在电话线上花多少钱。

【Input】

输入文件的第一行包含三个用空格隔开的整数：N，P和K

第二行到第P+1行:，每行分别都为三个用空格隔开的整数：Ai，Bi和Li

【output】

输出文件中仅包含一个整数，表示在这项工程上的最小支出。如果任务不可能完成，则输出-1。

【Sample Input】

5 7 1

1 2 5

3 1 4

2 4 8

3 2 3

5 2 9

3 4 7

4 5 6

【Sample Output】

题解

一开始想写分层图，可是看到k<=1000就被吓尿了...果断写了二分答案，不过据说有队友分层图写AC了的...exm???总之两种都可以写

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<queue>
  5 #define maxn 1005
  6 #define inf 1<<29
  7 using namespace std;
  8 int n,p,k;
  9 int d[maxn],vis[maxn],map[maxn][maxn],tmp[maxn][maxn];
 10 void spfa1()
 11 {
 12     queue<int> q;
 13     for(int i=1 ; i<=n ; ++i)
 14         {
 15             d[i]=inf;
 16             vis[i]=0;
 17         }
 18     vis[1]=1;
 19     d[1]=0;
 20     q.push(1);
 21     while(!q.empty())
 22     {
 23         int dd=q.front();q.pop();
 24         vis[dd]=0;
 25         for(int i=1 ; i<=n ; ++i )
 26             if(map[dd][i])
 27                 if(d[dd]+1<d[i])
 28                 {
 29                     d[i]=d[dd]+1;
 30                     if(!vis[i])
 31                     {
 32                         vis[i]=1;
 33                         q.push(i);
 34                     }
 35                 }
 36     }
 37 }
 38 void spfa()
 39 {
 40     queue<int> q;
 41     for(int i=1 ; i<=n ; ++i)
 42         { 
 43             d[i]=inf;
 44             vis[i]=0;
 45         }
 46     vis[1]=1;
 47     d[1]=0;
 48     q.push(1);
 49     while(!q.empty())
 50     {
 51         int dd=q.front();q.pop();
 52         vis[dd]=0;
 53         for(int i=1 ; i<=n ; ++i )
 54             if(map[dd][i])
 55                 if(d[dd]+tmp[dd][i]<d[i])
 56                 {
 57                     d[i]=d[dd]+tmp[dd][i];
 58                     if(!vis[i])
 59                     {
 60                         vis[i]=1;
 61                         q.push(i);
 62                     }
 63                 }
 64     }
 65 }
 66 int cal(int x)
 67 {
 68     for(int i=1 ; i<=n ; ++i)
 69         for(int j=i ; j<=n ; ++j)
 70             if(map[i][j]>x)tmp[i][j]=tmp[j][i]=1;
 71             else tmp[i][j]=tmp[j][i]=0;
 72     spfa();
 73     return d[n];
 74 }
 75 int main()
 76 {
 77     freopen("phone.in","r",stdin);
 78     freopen("phone.out","w",stdout);
 79     int u,v,w;
 80     scanf("%d%d%d",&n,&p,&k);
 81     for(int i=1 ; i<=p ; ++i )
 82     {
 83         scanf("%d%d%d",&u,&v,&w);
 84         map[u][v]=map[v][u]=w;
 85     }
 86     spfa1();
 87     if(d[n]<=k)
 88     {
 89         printf("0");
 90         return 0;
 91     }
 92     int l=1,r=1000000;
 93     while(r>l)
 94     {
 95         int m=(l+r)>>1;
 96         if(cal(m)>k)l=m+1;
 97         else r=m;
 98     }
 99     if(r==1000000)printf("-1");
100     else printf("%d",r);
101     return 0;
102 }

Road(Road)

【问题描述】

有N个村庄编号从1~N。小G要建一些路，使每两个村庄都连通。连通的定义为：如果A和B直接相连，则A&B连通。如果A&C连通，B&C连通，则A&B连通。小G发现有些村庄间已经有路，小G想知道修路的最小总长度是多少。

【Input】

第一行一个正整数N，表示村庄的数量。

接下来N行每行N个数，第i行第j个数表示从i到j的距离D。

接下来一个正整数M，表示已经存在的边的数量。

接来下M行每行两个正整数，表示已经存在的边连接的两个村庄的编号。

【output】

一个整数，表示使所有村庄两两相连的最短修路距离。

【Sample Input】

0 990 692

990 0 179

692 179 0

1 2

【Sample Output】

179

【数据范围】

3<=N<=100

1<=D<=1000

0<=M<=N*(N+1)/2

题解

裸的kruskal，这里提供另外一种写法,Floyd传递闭包，考试的时候写炸了mmp，和傻逼一样的自己...

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 #define maxn 105
 7 int link[maxn][maxn],map[maxn][maxn];
 8 int ans,n,m,sum,cnt;
 9 void floyd()
10 {
11     for(int k=1 ; k<=n ; ++k)
12         for(int i=1 ; i<=n ; ++i)
13             if(link[i][k])
14             for(int j=i+1 ; j<=n ; ++j)
15                 if(link[k][j])link[i][j]=link[j][i]=1;
16 }
17 struct edge{
18     int u,v,w;
19 }E[maxn*maxn];
20 void add(int u,int v)
21 {
22     E[++cnt].u=u;
23     E[cnt].v=v;
24     E[cnt].w=map[u][v];
25 }
26 bool cmp(edge x,edge y){return x.w<y.w;}
27 int main()
28 {
29 //    freopen("road.in","r",stdin);
30 //    freopen("road.out","w",stdout);
31     int u,v;
32     scanf("%d",&n);
33     for(int i=1 ; i<=n ; ++i )
34         for(int j=1 ; j<=n ; ++j )
35             scanf("%d",&map[i][j]);
36     scanf("%d",&m);
37     for(int i=1 ; i<=n ; ++i)link[i][i]=1;
38     for(int i=1 ; i<=m ; ++i)
39         {
40             scanf("%d%d",&u,&v);
41             link[u][v]=link[v][u]=1;
42         }
43     floyd();
44     for(int i=1 ; i<=n ; ++i)
45         for(int j=i+1 ; j<=n ; ++j)
46             if(link[i][j]==0)add(i,j);
47     sort(E+1,E+1+cnt,cmp);
48     for(int i=1 ; i<=cnt ; ++i )
49     {
50         int u=E[i].u,v=E[i].v;
51         if(link[u][v])continue;
52         int w=E[i].w;
53         sum+=w;
54         link[u][v]=link[v][u]=1;
55         for(int k=1 ; k<=n ; ++k )
56             if(link[u][k])
57                 for(int p=1 ; p<=n ; ++p)
58                     if(link[v][p])link[k][p]=link[p][k]=1;
59     }
60     printf("%d",sum);
61     return 0;
62 }

　　 Sightseeing

【问题描述】

小G计划在暑假去北京旅游。她已经知道了n个景点和景点间交通的路费，并确定好了起点和终点。为了节省路费，小G当然会选择从起点到终点的最短路。两条路径上只要有一条边不同这两条路径就算作不同的路径（无重边）。她通过观察发现最短路的数量太少，这令她非常不爽，于是她决定比最短路长度大1的方案也可以采用。

【Input】

第一行为数据组数T，T不会超过5。

第二行两个正整数N&M，表示景点个数和边的数量。

接下来M行，每行三个整数A,B,L，表示从A到B的路径长为L（单向的）。

接下来一行为起点和终点。

【output】

共一行，表示最短路的数量+比最短路长1的路径数量。答案不会超过 10⁹。

【Sample Input】

4 10

3 2 1

1 3 1

3 1 1

2 4 1

1 2 1

4 1 1

3 2 1

4 1 1

3 1 1

3 2

4 10

3 4 2

3 1 1

4 2 1

1 3 1

1 2 3

3 4 2

4 3 1

4 3 3

3 4 3

3 4

【Sample Output】

【数据范围】

2<=N<=1000

1<=M<=10000

题解

一遍spfa找最短路，然后dfs寻找路径...

考试的时候很坚定的认为dfs过不了，10^9的数据啊...结果最大数据也只是100过一点

考试写了两个spfa，第二个记录每一个点达到最短路及最短路+1情况的方案数。因为判断+1成立的条件是dis[v]=dis[d]+w-1，因为题目写着单向边就很大胆的写了，结果这尼玛把一对双向边当成两个单向边输入了？？？what the fuck??全死循环了（边权为1的边会造成死循环，请自行思考）没脾气了，暴力出奇迹，暴力出奇迹...

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<queue>
  5 #define maxn 1005
  6 #define maxm 10005
  7 #define inf 1<<29
  8 using namespace std;
  9 int n,m,st,ed,ecnt;
 10 int dis[maxn],vis[maxn],cnt[maxn][3],head[maxn],ro[maxn][maxn];
 11 struct edge{
 12     int u,v,w,next;
 13 }E[maxm];
 14 void addedge(int u,int v,int w)
 15 {
 16     E[++ecnt].u=u;
 17     E[ecnt].v=v;
 18     E[ecnt].w=w;
 19     E[ecnt].next=head[u];
 20     head[u]=ecnt;
 21 }
 22 void spfa()
 23 {
 24     queue<int> q;
 25     for(int i=1 ; i<=n ; ++i)
 26     {
 27         vis[i]=0;
 28         dis[i]=inf;
 29     }
 30     dis[st]=0;vis[st]=1;
 31     q.push(st);
 32     while(!q.empty())
 33     {
 34         int dd=q.front();q.pop();
 35         vis[dd]=0;
 36         for(int i=head[dd] ; i ; i=E[i].next )
 37         {
 38             int v=E[i].v;
 39             int w=E[i].w;
 40             if(dis[v]>=dis[dd]+w)
 41             {
 42                 dis[v]=dis[dd]+w;
 43                 if(!vis[v])
 44                 {
 45                     vis[v]=1;
 46                     q.push(v);
 47                 }
 48             }
 49         }
 50     }
 51 }
 52 int dfs(int u,int sum)
 53 {
 54     int ret(0);
 55     if(sum>dis[ed]+1)return 0;
 56     if(u==ed&&(sum==dis[ed]||sum==dis[ed]+1))return 1;
 57     for(int i=head[u] ; i ; i=E[i].next )
 58     {
 59         int v=E[i].v;
 60         int w=E[i].w;
 61         if(vis[v])continue;
 62         vis[v]=1;
 63         ret+=dfs(v,sum+w);
 64         vis[v]=0;
 65     } 
 66      return ret;
 67 }
 68 int read()
 69 {
 70     int ret(0);
 71     char ch;
 72     ch=getchar();
 73     while(ch<‘0‘||ch>‘9‘)ch=getchar();
 74     while(ch>=‘0‘&&ch<=‘9‘)
 75     {
 76         ret=ret*10+ch-‘0‘;
 77         ch=getchar();
 78     }
 79     return ret;
 80 } 
 81 void init()
 82 {
 83     for(int i=1 ; i<=n ; ++i)
 84         head[i]=0;
 85     ecnt=0;
 86 }
 87 int main()
 88 {
 89     freopen("sightseeing.in","r",stdin);
 90     freopen("sightseeing.out","w",stdout);
 91     int T,u,v,w;
 92     scanf("%d",&T);
 93     while(T--)
 94     {
 95         scanf("%d%d",&n,&m);
 96         for(int i=1 ; i<=m ; ++i )
 97         {
 98             u=read();v=read();w=read();
 99             addedge(u,v,w);
100         }
101         scanf("%d%d",&st,&ed);
102         spfa();
103         for(int i=1 ; i<=n ; ++i )vis[i]=0;
104         vis[st]=1;
105         printf("%d
",dfs(st,0));
106         init();
107     }
108     return 0;
109 }

[考试反思]0515省选模拟97：构造(代码片段)

我好菜啊。。。数学不会数据结构不会博弈不会图论也不会，现在构造也不会了。。。今天看似来了俩构造。然而一个是凭空想象的结论题（好难证。。。）还有一个是提答于是我就凭空想象了，然而我菜所以猜错了，然后炸了... 查看详情

2021年ccpc女生专场（淄博）i.驾驶卡丁车（状压+模拟）

目录问题分析代码问题驾驶卡丁车-https://codeforces.com/gym/103389/problem/I2021年CCPC女生专场分析前进方向有8个双重循环状压：某个方格四周的平地及障碍物信息用8位二进制表示代码#include<bits/stdc++.h>usingnamespacestd;constintm... 查看详情

12.10图论专题

昨天考了图论考完简直万脸懵逼我学的是个啥球吗？？？考试居然还叫图论入门((自杀第一题重量不同的硬币主要是两遍遍历和bellmanford考试的时候只遍历了一遍有很多漏洞只拿了12分第二题考最大生成树((还有异或结果考试的时... 查看详情

2021年ccpc女生专场（淄博）i.驾驶卡丁车（状压+模拟）(代码片段)

7.3图论模拟

FJSC图论测试题目 1.无线通讯网（wireless.pas/cpp/c）【题目描述】国防部计划用无线网络连接若干个边防哨所。2种不同的通讯技术用来搭建无线网络；每个边防哨所都要配备无线电收发器；有一些哨所还可以... 查看详情

关于省赛模拟赛（迪迦桑专场）

这一次的小比赛，因为全是英文题，导致了我们队的心态有点崩，以前很少打这种全是英文的比赛，但是我们明知道以后还会打这种比赛，却没有提前做好准备。　　这一次的比赛我们全程跟着榜单走，我们队... 查看详情

疫情延迟noip模拟二分答案图论

题面在最下方。首先最短路判断一下有没有输出-1 的情况。然后把握答案可以二分求解的特点，那就很容易解决了。令边中最大的年代为 maxx那么就在[1,maxx]中进行二分求解，枚举年代mid，跑一遍最短路，不走年代<=mid... 查看详情

东北育才数论专场第2场

...发现规律后乱搞。（居然给时6s）　　beetle离散化后BFS，模拟。　　divisorful这道题打打表就够了。（恶心，想吐）　　居然rank1，不想多说了。　　查看详情

2016弱校联萌十一专场10.3遗憾题合集

http://acm-icpc.aitea.net/index.php?2016%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95C.Wedon‘twannawork!@siludose你要的代码，做好了参考看SB模拟，xjb模拟#include<iostream& 查看详情

2021年ccpc女生专场（淄博）i.驾驶卡丁车（状压+模拟）(代码片段)

2017中国大学生程序设计竞赛-女生专场（重现）

A.AutomaticJudge(模拟)ProblemDescriptionWelcometoHDUtotakepartinthesecondCCPCgirls’competition!Anewautomaticjudgesystemisusedforthiscompetition.Duringthefive-hourcontesttime,youcansubmityourcodeto 查看详情

[考试反思]图论专题测试：怀疑(代码片段)

没写完，但是好像有人需要代码，于是先发布出来。回去之后记得贴排行榜。0+0+55.rk11.考场上想出了T1的三分，不确定，没有写。写了另一个好像靠谱点的二分，但是好像写挂了。。。T2没读题，又是没读题，又是没读题！... 查看详情

rhce模拟考试

...这些虚拟机的系统登陆密码请留意当时的考试细则说明。模拟考试环境说明：您有三台虚拟机，分别是classroom-rh254,server-rh254,de 查看详情

[考试反思]0214省选模拟24：揣测(代码片段)

还行吧。至少不算炸。虽说这个分的确也不怎么样。考试的时候觉得$T2$是个计数，部分分好像还挺多，应该可想。然后在$T2$上刚了仨小时，因为做的题不够会的知识点也不够所以只有签到分。$T1$的话贪心暴力随便写就是了用不... 查看详情

阿里巴巴专场——第322场周赛题解(代码片段)

目录模拟法：6253.回环句排序后模拟：6254.划分技能点相等的团队BFS：6255.两个城市间路径的最小分数BFS：6256.将节点分成尽可能多的组模拟法：6253.回环句这道题直接按照题目的意思暴力模拟即可：classSo... 查看详情

20171010

当前最好成绩：noip2016初赛32.5模拟赛（3）：140模拟赛（6）：270评级：零九月的最后几天，肝了两道图论之后开始研究一些稀奇古怪的问题，然后就去辅导了。听课之后才发现，这明明就是一个省选的班，一共只有我校与另... 查看详情

图论-最小生成树

...第二作者讲的课程，关于最小生成树的算法。其实就是先模拟一下小样例（不是单纯模拟，而是发现其中的规律，要思考）然后发现最优子结构-如果（u,v）是一条唯一连接两点的边，那么将原图拆分为两块（一块包含u，一块包... 查看详情

$noip2016day1$模拟考试题解报告(代码片段)

没有摘要的摘要目录$NOIP\\2016\\Day1$模拟考试题解报告得分情况考试过程题解$T1$玩具谜题$T2$天天爱跑步$T3$换教室\$NOIP\\2016\\Day1\$模拟考试题解报告得分情况\$T1\$\$85\\Pts\$\$T2\$\$15\\Pts\$\$T3\$\$100\\Pts\$总分:\$200\\Pts\$考试过... 查看详情