程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [BZOJ 2753][SCOI2012]滑雪與時間膠囊

[BZOJ 2753][SCOI2012]滑雪與時間膠囊

編輯:C++入門知識

Description

a180285非常喜歡滑雪。他來到一座雪山,這裡分布著M條供滑行的軌道和N個軌道之間的交點(同時也是景點),而且每個景點都有一編號i(1<=i<=N)和一高度Hi。a180285能從景點i 滑到景點j 當且僅當存在一條i 和j 之間的邊,且i 的高度不小於j。 與其他滑雪愛好者不同,a180285喜歡用最短的滑行路徑去訪問盡量多的景點。如果僅僅訪問一條路徑上的景點,他會覺得數量太少。於是a180285拿出了他隨身攜帶的時間膠囊。這是一種很神奇的藥物,吃下之後可以立即回到上個經過的景點(不用移動也不被認為是a180285 滑行的距離)。請注意,這種神奇的藥物是可以連續食用的,即能夠回到較長時間之前到過的景點(比如上上個經過的景點和上上上個經過的景點)。 現在,a180285站在1號景點望著山下的目標,心潮澎湃。他十分想知道在不考慮時間 膠囊消耗的情況下,以最短滑行距離滑到盡量多的景點的方案(即滿足經過景點數最大的前提下使得滑行總距離最小)。你能幫他求出最短距離和景點數嗎?

Input

輸入的第一行是兩個整數N,M。 接下來1行有N個整數Hi,分別表示每個景點的高度。 接下來M行,表示各個景點之間軌道分布的情況。每行3個整數,Ui,Vi,Ki。表示 編號為Ui的景點和編號為Vi的景點之間有一條長度為Ki的軌道。

Output

輸出一行,表示a180285最多能到達多少個景點,以及此時最短的滑行距離總和。

Sample Input


3 3
3 2 1
1 2 1
2 3 1
1 3 10

Sample Output

3 2

HINT

【數據范圍】

對於30%的數據,保證 1<=N<=2000

對於100%的數據,保證 1<=N<=100000

對於所有的數據,保證 1<=M<=1000000,1<=Hi<=1000000000,1<=Ki<=1000000000。

Source

媽的BZOJ坑啊,M的數據范圍是[1,2000000],坑死我N次了

第一問BFS很明顯不解釋,第二問是最小樹形圖。。。但是這題是有向圖又不好做,最小生成樹只能對付無向圖,可題目范圍大得嚇人,還是用kruscal,只對可以和起點聯通的邊跑kruscal,邊的預處理就對邊的高度(這裡看邊的終點高度,因為終點高度小於起點高度)降序排序,高度相同時就按邊權升序排序,kruscal就ok了

很令人費解的是為什麼邊兩端高度相同時要建雙向邊呢,難道一個路沒坡的話還能滑?真是奇怪,在這裡也被狠狠地坑了下

//題目大意:求有向圖的最小生成樹
#include 
#include 
#include 
#include 
#include 
#define MAXN 100050
#define MAXM 2000050
using namespace std;
struct Line
{
	int u,v; //起點、終點
	int w; //邊權
	int next; //下一條邊
}edge[MAXM]; //邊集
queueq; //bfs用隊列
int f[MAXN]; //並查集用
long long int dis=0; //dis=最短距離
int n,m,cnt=0,tot=0,visit[MAXN],high[MAXN]; //cnt=可經過的點總數,tot=有效邊的總數,visit[i]=1表示點i訪問過,high[i]=點i的高度
int head[MAXM];
int cmp(Line a,Line b) //先按邊的終點高度降序排序,高度相同的按邊權升序排序
{
	return high[b.v]t,邊權為n
{
	edge[tot].u=s;
	edge[tot].v=t;
	edge[tot].w=n;
	edge[tot].next=head[s];
	head[s]=tot++;
}
void init()
{
	int i,j;
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d",&high[i]);
	for(i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(high[u]>=high[v]) AddLine(u,v,w); //加邊
		if(high[v]>=high[u]) AddLine(v,u,w);
	}
}
void bfs() //bfs找可走的路
{
	int i,x;
	q.push(1);
	visit[1]=1; //非常重要!!!
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		cnt++;
		for(i=head[x];i!=-1;i=edge[i].next)
		{
			int y=edge[i].v; //下一條邊的終點
			if(!visit[y])
			{
				visit[y]=1;
				q.push(y); //若該點未被訪問過,標記,入隊
			}
		}
	}
}
void kruscal() //kruscal求最小生成樹
{
	int i,j,rootu,rootv,u,v;
	sort(edge,edge+tot,cmp);
	for(i=1;i<=n;i++) f[i]=i; //並查集初始化
	for(i=0;i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved