山东大学计算机科学与技术学院程序设计思维与实践作业
山大程序设计思维与实践作业
sdu程序设计思维与实践
山东大学程序设计思维实践作业H7
山大程序设计思维实践作业H7
山东大学程序设计思维与实践
week7-图和树的性质与应用（中）

相关资料：GitHub

A : 卖菜

问题描述
　　在一条街上有 n 个卖菜的商店，按 1 至 n 的顺序排成一排，这些商店都卖一种蔬菜。
　　第一天，每个商店都自己定了一个价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。
　　注意，编号为 1 的商店只有一个相邻的商店 2，编号为 n 的商店只有一个相邻的商店 n-1，其他编号为 i 的商店有两个相邻的商店 i-1 和 i+1。
　　给定第一天各个商店的菜价，请计算第二天每个商店的菜价。

输入格式
输入的第一行包含一个整数 n，表示商店的数量。
　　第二行包含 n 个整数，依次表示每个商店第一天的菜价。

输出格式
输出一行，包含 n 个正整数，依次表示每个商店第二天的菜价。

样例输入
8
4 1 3 1 6 5 17 9
样例输出
2 2 1 3 4 9 10 13
数据规模和约定
对于所有评测用例，2 ≤ n ≤ 1000，第一天每个商店的菜价为不超过 10000 的正整数。

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int *yjiage=new int[n];
	memset(yjiage,0,sizeof(yjiage));
	int *pjiage=new int[n];
	memset(pjiage,0,sizeof(pjiage));
	for(int i=0;i<n;i++)
	cin>>yjiage[i];
	pjiage[0]=(yjiage[0]+yjiage[1])/2;
	pjiage[n-1]=(yjiage[n-2]+yjiage[n-1])/2;
	for(int j=1;j<n-1;j++)
	{
		pjiage[j]=(yjiage[j-1]+yjiage[j]+yjiage[j+1])/3;
	}
	for(int x=0;x<n;x++)
	cout<<pjiage[x]<<" ";
	cout<<endl;
	return 0;
}

B : 买菜

问题描述
　　小 H 和小 W 来到了一条街上，两人分开买菜，他们买菜的过程可以描述为，去店里买一些菜然后去旁边的一个广场把菜装上车，两人都要买 n 种菜，所以也都要装 n 次车。具体的，对于小 H 来说有 n 个不相交的时间段[a1,b1],[a2,b2]…[an,bn]在装车，对于小 W 来说有 n 个不相交的时间段[c1,d1],[c2,d2]…[cn,dn]在装车。其中，一个时间段[s, t]表示的是从时刻 s 到时刻 t 这段时间，时长为 t-s。
　　由于他们是好朋友，他们都在广场上装车的时候会聊天，他们想知道他们可以聊多长时间。
输入格式
输入的第一行包含一个正整数 n，表示时间段的数量。
　　接下来 n 行每行两个数ai，bi，描述小 H 的各个装车的时间段。
　　接下来 n 行每行两个数ci，di，描述小 W 的各个装车的时间段。
输出格式
输出一行，一个正整数，表示两人可以聊多长时间。
样例输入
4
1 3
5 6
9 13
14 15
2 4
5 7
10 11
13 14
样例输出
3

#include <bits/stdc++.h>
using namespace std;


int h[1000010]={0};
int w[1000010]={0};
int n;
int main()
{
	cin>>n;
	int shijian=0;
	int a,b,c,d;
	for(int i=0;i<n;i++)
	{
		cin>>a>>b;
		for(int j=a;j<b;j++) h[j]=1;
	}
	for(int i=0;i<n;i++)
	{
		cin>>c>>d;
		for(int j=c;j<d;j++) w[j]=1;
	}
	
	for(int i=0;i<1e6+10;i++)
	{
		if(h[i]==1&&w[i]==1)
		{
			shijian++;
		}
	}
	
	cout<<shijian;
	
	
	
	
	return 0;
 } 

C : 穿越虫洞

问题描述
小 H 有n个秘密基地（编号 1 到 n ）,n 个秘密基地之间有 m 条双向路径和 w 个单向时空隧道，通过路径需要消耗一定的时间T
i
​
，而通过时空隧道可以使时光倒流T
j
​
,现在小 H 想知道他能否从某一秘密基地出发，通过路径和时空隧道回到过去（即回到出发的秘密基地且该时刻要早于出发时间）。

输入格式
第1行，一个整数 F,表示测试用例的数量
接下来对于每一个测试用例，输入格式如下
第1行，三个空格分隔的整数n,m,w
第2到 m+1 行，三个空格分隔的数字 s,e,t，表示 s,e 之间存在双向道路，通行需要消耗t，允许两点间存在多条路径
第m+2到m+w+1行三个空间分隔的数字 s,e,t,表示存在从 s 到 e 的单向时空隧道，穿过时空隧道时光倒流 t

输出格式
对于每个测试用例，如果小 H 能回到过去则输出 YES，否则输出 NO
每个测试用例的输出占一行

样例输入
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
样例输出
NO
YES

NO
YES

#include <iostream>
using namespace std;
int edge[501][501];
int ds[501][501];
void chushihua(){
    for (int i = 0; i < 501; ++i){
        for (int j = 0; j < 501; ++j){
            edge[i][j] = 10000;
        }
    }
}

void fuzhi(){
    for(int i = 0;i<501;i++){
        for(int j = 0;j<501;j++){
            ds[i][j] = edge[i][j];
        }
    }
}

void output(int n){
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            printf("%d ",ds[i][j]);
        }
        printf("\n");
    }
}

int main(){
    int tes = 0;
    scanf("%d",&tes);//有多少个例子

    for (int i = 0; i < tes; ++i){
        chushihua();//每轮初始化一遍
        int n,m,w;
        scanf("%d %d %d",&n,&m,&w);//n为基地数，m为双向边数,w为时空隧道数量
        for (int j = 0; j < m; ++j){
            int s,e,t;
            scanf("%d %d %d",&s,&e,&t);
            if(edge[s][e]>t){//如果对应点耗时比新的大
                //要看是不是有负路径，则储存最小的边即可
                edge[s][e] = t;
                edge[e][s] = t;//由于是双向边，故所有两个都要改
            }
        }
        for (int i = 0; i < w; ++i){
            int s,e,t;
            scanf("%d %d %d",&s,&e,&t);
            if(edge[s][e]>(-t)) edge[s][e] = -t;//如果这个边的值比t的负数大，则修改该值
        }

        fuzhi();//把edge值拷贝到ds数组中
        for(int k = 1;k<=n;k++){
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=n;j++){
                    ds[i][j] = min(ds[i][j],ds[i][k]+ds[k][j]);
                }
            }
        }

        bool is = false;
        for(int i = 0;i<501;i++){
            if(is) break;
            for(int j = 0;j<501;j++){
                if(edge[j][i]!=10000&&ds[i][j]+edge[j][i]<0) {
                    printf("YES\n");
                    is = true;
                    break;
                }
            }
        }
        if(!is) printf("NO\n");
    }
    return 0;
}

D : 差旅花费

问题描述
有 n 个车站，其中 1 号车站为始发站，现有 n-1 个人，你需要安排他们分别去往除始发站以外的 n-1 个车站，然后返回始发站。交通系统的所有路径均为单向路径，连接两个不同的车站，每经过一条路径需要交纳一定的费用，你能求出总花费的最低金额嘛

输入格式
第一行一个整数 T，表示测试用例的个数。
对于每个测试用例，输入格式如下
第一行两个整数 n,m,分别表示车站的数量和车站之间的单向路径数。
接下来 m 行，每行三个数 s,e,c,表示存在从 s 到 e 的单向路径，花费为 c

输出格式
对于每个测试用例，输出其总花费的最低金额，每个测试用例的输出占一行。

样例输入
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
样例输出
46
210

#include<bits/stdc++.h>
using namespace std;
#define N 2000100
#define inf 1e9
int T;
int n,m;
int s,e,c;
int pnt1[N],v1[N],nxt1[N],weight[N];
int pnt2[N],v2[N],nxt2[N];
int dis[N],vis[N];
int t= 0;
void add(int x,int y, int z){
    t++;
    nxt1[t] = pnt1[x]; pnt1[x] = t; v1[t] = y;
    nxt2[t] = pnt2[y]; pnt2[y] = t; v2[t] = x;
    weight[t] = z;}
void Dijkstra_1(int s){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>> > q1;
    for(int i = 1; i <= N; i++)
        dis[i] = inf, vis[i] = 0;
    dis[s] = 0;
    q1.push(make_pair(0,s));
    while(!q1.empty()){
        int x = q1.top().second;
        q1.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = pnt1[x]; i; i = nxt1[i])
            if(dis[v1[i]] > dis[x] + weight[i]){
                dis[v1[i]] = dis[x] + weight[i];
                q1.push(make_pair(dis[v1[i]],v1[i]));
            }
    }
}
void Dijkstra_2(int s){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>> > q2;
    for(int i = 1; i <= N; i++)
        dis[i] = inf, vis[i] = 0;
    dis[s] = 0;
    q2.push(make_pair(0,s));
    while(!q2.empty()){
        int x = q2.top().second;
        q2.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = pnt2[x]; i; i = nxt2[i])
            if(dis[v2[i]] > dis[x] + weight[i]){
                dis[v2[i]] = dis[x] + weight[i];
                q2.push(make_pair(dis[v2[i]],v2[i]));
            }
    }
}
int main(){
    scanf("%d",&T);
    for(int i = 0; i < T; i++){
        long long sum = 0;
        scanf("%d%d",&n,&m);
        t= 0;
        for(int i = 1; i <= N; i++){
            pnt1[i] = 0, pnt2[i] = 0,
            v1[i] = 0, v2[i] = 0;
            nxt1[i] = 0, nxt2[i] = 0;
            weight[i] = 0;
        }
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d",&s,&e,&c);
            add(s,e,c);
        }
        Dijkstra_1(1);
        for(int i = 2; i <= n; i++)
            sum += (long long)dis[i];
        Dijkstra_2(1);
        for(int i = 2; i <= n; i++)
            sum += (long long)dis[i];
        printf("%lld\n",sum);
    }
    return 0;
}

E : 运输货物

问题描述
考虑一个具有 N 个顶点，M 条边的无向图。编号为 1 的顶点对应于一个矿山，从中提取一些珍贵的矿物。编号为 N 的顶点对应于一家矿物加工厂。每条边连接两个不同的顶点并拥有有两个参数，分别为最大承重量 C 和通行时间 D。现在将从矿山中提取的矿物并选择一条路径将提取的矿物运送至工厂。该路径应具有最大的承重量，以便能够同时运输尽可能多的矿物。路径的承重量等于路径中经过的边的最大承重量的最小值。但是，这些矿物非常敏感，一旦从矿山中提取出来，它们将在 T 时间单位后开始分解，除非他们在此时间间隔内到达工厂。因此，所选路径的总行进时间（其路径的通行时间之和）应小于或等于 T。

输入格式
输入的第一行包含一个整数 X，表示测试用例的数量。
每个测试用例的第一行包含 3 个整数，并用空格分隔：N，M，T。接下来的 M 行中的每行将包含四个整数，每个数字用空格分隔：A，B，C 和 D，这意味着顶点 A 和 B 之间存在一条边，最大承重量为 C，通行时间为 D。A 和 B 是 1 和 N 之间的不同整数。任何两个顶点之间最多存在一个边。

输出格式
对于 X 个测试用例，请输出在满足通行时间限制下的路径最大承重量，每个测试用例对应一行。
数据保证图中至少存在一条 1 到 n 通行总时间小于等于 T 的路径，即一定有解。

样例输入
2
2 1 10
1 2 13 10
4 4 20
1 2 1000 15
2 4 999 6
1 3 100 15
3 4 99 4
样例输出
13
99

13
99

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int inf=1e8;
const int maxin=1e5+5;
const int maxim=1e6+5;
struct Edge{
    ll v,w,t,next;//v,c,d
}Edges[2*maxin];
ll tot;
ll head[maxin];
void init(int n){
    tot=0;
    for(int i=1;i<=n;++i) head[i]=-1;
}
void addEdge(ll u,ll v,ll w,ll t){
    Edges[tot].v=v;
    Edges[tot].w=w;
    Edges[tot].t=t;
    Edges[tot].next=head[u];
    head[u]=tot++;
}
ll dis[maxin];//time
bool vis[maxin];//vis：节点i有没有被弹出堆
ll n,m,t;//秘密基地数，双向路径数，单向时空隧道数
ll weia[maxin];
void dijkstra1(ll s,ll wei){
    priority_queue<pii,vector<pii>,greater<pii> > pq;//小根堆
    for(int i=1;i<=n;++i) dis[i]=inf,vis[i]=0;
    dis[s]=0;
    pq.push({0,s});//dis,posi
    while(!pq.empty()){
        ll u=pq.top().second;//posi
        pq.pop();
        if(vis[u]) continue;//已弹出的
        vis[u]=1;
        for(int i=head[u];i!=-1;i=Edges[i].next)
            if((dis[Edges[i].v]>dis[u]+Edges[i].w)&&wei<=Edges[i].t){
                dis[Edges[i].v]=dis[u]+Edges[i].w;
                pq.push({dis[Edges[i].v],Edges[i].v});
            }
    }
}
int main(){
    ll x;cin>>x;
    ll a,b,c,d;
    while(x--){
        cin>>n>>m>>t;//1,n,1e4; 1,m,5e4; 1,t,5e5
        //N 个顶点，M 条边的无向图,所选路径的总行进时间（其路径的通行时间之和）应小于或等于 T
        init(n);
        set<ll> wei;
		for(ll i=0;i<m;++i){
            cin>>a>>b>>c>>d;//1,a,v,n; 1,c,1e7; 1,d,1e4
            //A 和 B 之间存在一条边，最大承重量为 C，通行时间为 D
            addEdge(a,b,d,c);
            addEdge(b,a,d,c);
            wei.emplace(c);
        }
        ll l=0;ll r=wei.size()-1;ll i=0;
        for(auto &x:wei){
        	weia[i++]=x;
		}
        while((r-l)>1){
        	int mid=(r+l)/2;
        	dijkstra1(1,weia[mid]);
        	if(dis[n]>t) r=mid;
        	else l=mid;
		}
        cout<<weia[l]<<'\n';
    }
    return 0;
}