题目地址：POJ 2263
这题是在网上的一篇关于优先队列的博文中看到的。。但是实在没看出跟优先队列有什么关系。。我用的二分+并查集做出来了。。。
二分路的载重量。然后用并查集检查是否连通。
代码如下：
#include #include #include #include #include #include #include #include #include using namespace std; struct node { int u, v, w; }bian[20000]; int bin[300], n, tot; int find1(int x) { return bin[x]==x?x:bin[x]=find1(bin[x]); } void merger(int x, int y) { int f1=find1(bin[x]); int f2=find1(bin[y]); if(f1!=f2) { bin[f2]=f1; } } int main() { int m, x, s, t, max1, ans, num=0, i; char s1[100], s2[100]; map q; q.clear(); while(scanf("%d%d",&n,&m)!=EOF&&n&&m) { num++; tot=0; max1=-1; for(i=0;i >1; for(i=1;i<=n;i++) bin[i]=i; for(i=0;i =mid) { merger(bian[i].u,bian[i].v); } } if(find1(bin[s])==find1(bin[t])) { low=mid+1; ans=mid; } else { high=mid-1; } } printf("Scenario #%d\n%d tons\n\n",num,ans); } return 0; }