首页 > 代码库 > poj3662

poj3662

2024-07-09 23:52:43   221人阅读

题目大意：有n个节点p条无向边，现在可以选择其中的任意K条免费，如果必须的边多与K跳，则花费多余所需边中权值最大的一个，求最小花费多少。

分析：最短路+二分

我们可以二分答案mid,对于每一个mid求最短路，将最短路中大权值大于mid的边作为免费的集合，否则作为不免费的集合，验证免费集合大小是否大于K

这里有个技巧，就是在求最短路的过程中，把大于mid的边权值变为1，小于的为0那么最后求到的d[e]（e为终点）就是需要统计的集合大小

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<vector> 9 #define maxn 101010 #define maxm 100001011 #define INF 0x3fffffff12 using namespace std;13 struct edge {14     int to,w;15     edge(){}16     edge(int _to,int _w){17         to=_to;w=_w;18     }19 };20 typedef pair<int,int> P;21 int V;22 vector<edge> G[maxn];23 int d[maxn];24 int K;25 int dijkstra(int s,int x){26     priority_queue<P,vector<P>,greater<P> >q;27     for(int i=0;i<V;++i)d[i]=INF;28     d[s]=0;29     q.push(P(d[s],s));30     while(!q.empty()){31         P p = q.top();32         q.pop();33         int v = p.second;34         if(d[v]<p.first)continue;35         for(int i=0;i<G[v].size();++i){36             edge e = G[v][i];37             int dd = d[v]+(e.w>=x?1:0);38             if(d[e.to]>dd){39                 d[e.to]=dd;40                 q.push(P(d[e.to],e.to));41             }42         }43     }44     return d[V-1];45 }46 void solve(){47     int l =0,r = maxm+10;48     while(r-l>1){49         int mid = (l+r)/2;50         if(dijkstra(0,mid)>K)l=mid;51         else r=mid;52     }53     int ans = l;54     if(l>maxm)ans=-1;55     printf("%d\n",ans);56 }57 int main (){58     int n,m;59     while(scanf("%d%d%d",&n,&m,&K)!=EOF){60         for(int i=0;i<=n;++i)G[i].clear();61         V=n;62         int u,v,w;63         for(int i=0;i<m;++i){64             scanf("%d%d%d",&u,&v,&w);65             G[u-1].push_back(edge(v-1,w));66             G[v-1].push_back(edge(u-1,w));67         }68         solve();69     }70 }
View Code

 


联系
我们