本文共 3656 字，大约阅读时间需要 12 分钟。

我先给了18年的第三题

瓜农王大爷去年种西瓜赚了不少钱。看到收入不错，今年他又重新开辟了n个西瓜地。

为了能给他的n个西瓜地顺利的浇上水，对于每个西瓜地他可以选择在本地打井，也可以修管道从另一个瓜地（这个瓜地可能打了井；也可能没打井，他的水也是从其他瓜地引来的）将水引过来。

当然打井和修管道的费用有差别。已知在第i个西瓜地打井需要耗费wi元，在第i、j个西瓜地之间修管道需要耗费pi,j元。

现在的问题是：王大爷要想使所有瓜地都被浇上水，至少需要花费多少钱（打井与修管道的费用和）？

由于瓜地较多，王大爷无法选择在哪些（个）瓜地打井，哪些西瓜地之间修管道。

请你编程帮王大爷做出决策，求出最小费用。

（1<=N<=300，1<=wi<=100000；pi,i=0，1<=pi,j=pj,i<=100000）

input

第1行，一个正整数n，代表西瓜地的数量。

以下n行，依次给出整数w1…wn（每块西瓜地的打井费用）。

紧接着是一个n*n的整数矩阵，矩阵的第i行第j列的数代表pi,j（两块西瓜地之间建立管道的费用）。每行的两个数之间有一个空格隔开。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;//瓜农王大爷去年种西瓜赚了不少钱。看到收入不错，今年他又重新开辟了n个西瓜地。 //为了能给他的n个西瓜地顺利的浇上水，对于每个西瓜地他可以选择在本地打井，也可以修管道从另一个瓜地（这个瓜地可能打了井；也可能没打井，他的水也是从其他瓜地引来的）将水引过来。 //当然打井和修管道的费用有差别。已知在第i个西瓜地打井需要耗费wi元，在第i、j个西瓜地之间修管道需要耗费pi,j元。 //现在的问题是：王大爷要想使所有瓜地都被浇上水，至少需要花费多少钱（打井与修管道的费用和）？ //由于瓜地较多，王大爷无法选择在哪些（个）瓜地打井，哪些西瓜地之间修管道。 //请你编程帮王大爷做出决策，求出最小费用。//这道题和我之前写过的类似，就是求最短路径，可以将打井的钱，当做是从原点到该水管的距离，这样就增加了一些距离//可以创建一个数组来存储第一位是起点，第二位是终点，值是对应距离//用到并查集    int a[100];//用来存对应点的祖宗    int zuzong(int x){
           //找到某个点的祖宗        if(a[x]==x)            return x;        else            return zuzong(a[x]);    }    bool check(int x,int y){
           //判断两点是否同一个祖宗，也就是在不在同一个集合        return zuzong(x)==zuzong(y);    }    void merge_1(int x,int y){
           //合并两个点到同一个祖宗，前提是他们不是同一个祖宗        a[zuzong(x)]=zuzong(y);    }    int dis[100][100];    int i,j;    int n;//西瓜地的数量 struct Y{
        int s,e,dis;//对应起点，终点，和对应距离}Gua[100];bool cmp(Y a,Y b){
       return a.dis
      
     
    
   

第一题

Problem Description

有一群人去电影院看电影。但电影院有个很奇怪的规定：成人只能分到数字奇数座位号，未满18岁的儿童只能分到数字为偶数的座位号。

Input

输入共有n个人去看电影(1<=n<1000)，接下来输入n个人的座位号，每个座位号用空格隔开

Output

依次输出此次看电影成人的人数以及成人在所有人中所占的比例、未成年人的人数以及未成年人在所有人中所占的比例，计算出的比例保留两位小数，每个输出用空格隔开

Sample Input

8 13 12 10 8 3 24 21 19

Sample Output

4 0.50 4 0.50

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;//第一题//Problem Description//有一群人去电影院看电影。但电影院有个很奇怪的规定：成人只能分到数字奇数座位号，未满18岁的儿童只能分到数字为偶数的座位号。//Input//输入共有n个人去看电影(1<=n<1000)，接下来输入n个人的座位号，每个座位号用空格隔开//Output//依次输出此次看电影成人的人数以及成人在所有人中所占的比例、未成年人的人数以及未成年人在所有人中所占的比例，计算出的比例保留两位小数，每个输出用空格隔开//Sample Input//8 13 12 10 8 3 24 21 19//Sample Output//4 0.50 4 0.50int main(){
       int i,n;//输入的人数    int sum1=0;    int sum2=0;    int a[100];    scanf("%d",&n);    for(i=0;i
      
     
    
   

Problem Description

有一个大容器，现在向其中加入若干铅锤的木板,每个木板的顶端坐标记为(i,yi)，如图

Input

输入共加入n个木板(1<=n<1000)，接下来输入n个数字表示加入的n个木板的高度，每个高度用空格隔开

Output

输出该容器最大能装多少体积的水（容器不允许倾斜）

Sample Input

8 1 8 6 4 5 3 7 2

Sample Output

35

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;//第二题，给n模板，输入n个值代表模板的高度，求最大容积//我感觉就直接暴力，两次for循环，i从0-n-1 然后J 从i+1 到n-1 直接求最大值int main(){
       int i,j,n;    scanf("%d",&n);    int a[100];    for(i=0;i
       
        mmax)            mmax=v;    }    printf("%d",mmax);}
       
      
     
    
   

Problem Description

有一群人，现在告诉你他们之间的朋友关系。若A与B是朋友，B是C的朋友，则A与C也是朋友。朋友关系都是双向的，即A与B是朋友，B与A也是朋友。那么A、B、C就在同一个“朋友圈”

Input

首先输入n,m表示有n个人，m对关系(1<=n<2000)，接下来有m行每一行表示一对关系（输入每个数字代表一个人）

Output

输出在当前输入关系的情况下“朋友圈”的数量

Sample Input

8 7

1 2

2 4

4 1

5 7

4 3

6 2

7 8

Sample Output

2

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;//第四题有点像是连通图， 求连通图的个数。那就是用dfs或者bfs,或者是用并查集，然后用一个coun++struct Y{
       int s,e;}fri[100];int a[100];int zuzong(int x){
       if(x==a[x])        return x;    else        return zuzong(a[x]);}bool  check(int x,int y){
       return zuzong(x)==zuzong(y);}void merge_1(int x,int y){
       a[zuzong(x)]=zuzong(y);}int main(){
       int n,m;//n个人，m种关系    int i,c=1;//初始值为1，假设都连通    scanf("%d%d",&n,&m);    for(i=0;i
      
     
    
   

转载地址：http://uufen.baihongyu.com/