? 題目大意：給出一個圖，頂點為1到n和一個值k，求出包含頂點1到頂點n的通路的子圖中，第k+1大的邊最短為多少？（若存在一條從1到n路徑邊數小于等于k，則返回0，若不存在通路，返回-1）

? 思路：一開始我連題都看錯了，還以為是動規，汗···

? 很顯然，此題不好從正面下手，即如果從找到路徑下手的話會變得相當棘手，于是想到枚舉邊，以某一邊作為子圖中第k+1大的邊，看是否是可行解：比它大的邊的權值為1，反之為0，用spfa算出1到n的最短路，若路徑長大于k則二分查找比m更大的邊，反之則查找更小的邊，并可用e[0]=0表示權值為零的邊（即路徑上邊數小于k），這樣就不難得出正確解了。算法時間為O(nlgn)。

代碼如下：

#include <iostream> #include <fstream> using namespace std; ifstream fin("phone.in"); ofstream fout("phone.out"); int graph[1001][1001],matrix[1001][1001]; bool status[10001]; typedef struct { int start,end; int w; }Bian; Bian bian[10001]; int d[1001]; int Q[10001]; int partion(Bian *a,int start,int end) { int j=start-1; Bian t; for(int i=start;i<=end;i++) { if(a[i].w<=a[end].w) { j++; t=a[i]; a[i]=a[j]; a[j]=t; } } return j; } int quicksort(Bian *a,int start,int end) { if(start>=end) return 0; int j=partion(a,start,end); quicksort(a,start,j-1); quicksort(a,j+1,end); return 0; } int initial(int n) { for(int i=0;i<=n;i++) d[i]=10000000; return 0; } int spfa(Bian *m,int n) { initial(n); d[1]=0; int head=1,tail=1,t=0,i=0,x=0; Q[1]=1; while(((tail+1)000)!=head) { t=Q[head]; head++; head%=10000; for(i=1;i<=graph[t][0];i++) { x=0; if(matrix[t][graph[t][i]]>m->w) x=1; if(d[graph[t][i]]>d[t]+x) { d[graph[t][i]]=d[t]+x; tail++; Q[tail]=graph[t][i]; tail%=10000; } } } return d[n]; } int bins(int n,int p,int start,int end,int k) { if((end<0||start>p)||(start>end)) return -1; int m=(start+end)/2; if(spfa(&bian[m],n)>k) return bins(n,p,m+1,end,k); else { int t=bins(n,p,start,m-1,k); if(t==-1) return m; return t; } } int main() { ios::sync_with_stdio(0); int N=0,P=0,K=0,i=0,x=0,y=0,z=0; fin>>N>>P>>K; for(i=1;i<=P;i++) { fin>>x>>y>>z; graph[x][0]++; graph[x][graph[x][0]]=y; graph[y][0]++; graph[y][graph[y][0]]=x; matrix[x][y]=z; matrix[y][x]=z; bian[i].start=x; bian[i].end=y; bian[i].w=z; } quicksort(bian,1,P); i=bins(N,P,0,P,K); if(i<0) fout<<-1<<endl; else fout<<bian[i].w<<endl; return 0; }

? 這道題說明將適當的對象作為枚舉對象是重要的思想方法。

轉載于:https://www.cnblogs.com/kliner/archive/2012/10/12/noi2008_2_phone.html

總結

以上是生活随笔為你收集整理的NOI导刊模拟2—电话网络 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

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