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

Time Limit:?50 Sec??Memory Limit:?128 MB
Submit:?2457??Solved:?859

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

?

?

【分析】

　　說實話我看的時候也覺得是最小樹形圖。【然后表示朱劉算法忘得差不多了。。

　　但其實這個MST可以搞定ORZ。。

　　首先BFS，把能到的點標記一下，順便求第一問。

　　你可以看成同一高度的SCC縮點（里面當然直接MST就好的了），那就是個分層圖，按高度大小分的話呢，是一個DAG。

　　DAG的話、跑朱劉是不會找到環的，于是你第一步就搞定了。【應該是這樣的意思吧，網上的人不知道干嘛。。

　　然后其實可以把上面整個過程合成一個，就是按照 ?第一鍵值為終點的高度，第二鍵值為邊的權值，跑MST ?就行了。

?

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 #define Maxn 1000010 9 #define Maxm 1000010 10 #define LL long long 11 12 int h[Maxn],fa[Maxn]; 13 struct node 14 { 15 int x,y,c,next; 16 }t[Maxm*2]; 17 int first[Maxn],len; 18 19 void ins(int x,int y,int c) 20 { 21 if(h[x]>h[1]) return; 22 t[++len].x=x;t[len].y=y;t[len].c=c; 23 t[len].next=first[x];first[x]=len; 24 } 25 26 bool cmp(node x,node y) {return (h[x.y]==h[y.y])?(x.c<y.c):(h[x.y]>h[y.y]);} 27 28 int a1=1,st; 29 LL a2=0; 30 bool vis[Maxn]; 31 queue<int > q; 32 void bfs() 33 { 34 memset(vis,0,sizeof(vis)); 35 vis[st]=1;q.push(st); 36 while(!q.empty()) 37 { 38 int x=q.front(); 39 for(int i=first[x];i;i=t[i].next) 40 { 41 int y=t[i].y; 42 if(!vis[y]) 43 { 44 a1++; 45 q.push(y); 46 vis[y]=1; 47 } 48 } 49 q.pop(); 50 } 51 } 52 53 int ffa(int x) 54 { 55 if(fa[x]!=x) fa[x]=ffa(fa[x]); 56 return fa[x]; 57 } 58 59 int main() 60 { 61 int n,m; 62 scanf("%d%d",&n,&m); 63 for(int i=1;i<=n;i++) scanf("%d",&h[i]); 64 len=0; 65 memset(first,0,sizeof(first)); 66 for(int i=1;i<=m;i++) 67 { 68 int x,y,c; 69 scanf("%d%d%d",&x,&y,&c); 70 if(h[x]<h[y]) swap(x,y); 71 if(h[x]==h[y]) {ins(x,y,c);ins(y,x,c);} 72 else ins(x,y,c); 73 } 74 st=1;bfs(); 75 sort(t+1,t+1+len,cmp); 76 for(int i=1;i<=n;i++) fa[i]=i; 77 for(int i=1;i<=len;i++) 78 { 79 if(!vis[t[i].x]||!vis[t[i].y]) continue; 80 if(ffa(t[i].x)!=ffa(t[i].y)) 81 { 82 a2+=t[i].c; 83 fa[ffa(t[i].x)]=ffa(t[i].y); 84 } 85 } 86 printf("%d %lld\n",a1,a2); 87 return 0; 88 } View Code

?

要開long long

?

2017-03-29?10:05:58

轉載于:https://www.cnblogs.com/Konjakmoyu/p/6638248.html

總結

以上是生活随笔為你收集整理的【BZOJ 2753】 2753: [SCOI2012]滑雪与时间胶囊 （分层最小树形图，MST）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。