luogu2323&bzoj1196 [HNOI2006]公路修建问题

luogu2323&bzoj1196 [HNOI2006]公路修建问题

​​复制

4 2 5 1 2 6 5 1 3 3 1 2 3 9 4 2 4 6 1 3 4 4 2 输出样例#1： 复制

4 2 1 3 2 5 1 输入样例#2： 复制

4 1 5 1 2 6 5 1 3 3 1 2 3 9 4 2 4 6 1 3 4 4 3 输出样例#2： 复制

3 2 1 4 2 5 2 首先可以贪心+最小生成树搞

确实可以贪心去搞 首先我们针对所有的边的c1进行排序 然后贪心的选出这k条边来 那么剩下的没选的以后也有可能选啊是不是 于是我们再一次针对所有没被选过的边的最小值进行一波排序的

为什么不把前面的排序因为已经选了 而没选的一定是产生了冲突所以每次贪心的选每条边的最小就行了 并且记录路径 当数量等于n-1的时候退出输出即可

include

include

define N 11000

using namespace std; inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while (ch<’0’||ch>’9’){if (ch==’-‘) f=-1;ch=gc();} while (ch<=’9’&&ch>=’0’){x=x*10+ch-‘0’;ch=gc();} return x*f; } struct node{ int x,y,c1,c2,id; }data[N<<1]; struct node1{ int id,op; }way[N]; int fa[N],n,k,m,num; inline bool cmp1(node a,node b){return a.c1

#include#include#define N 11000#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}int fa[N],n,m,k;inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}struct node{ int x,y,c1,c2;}data[N<<1];inline bool judge(int x){ for (int i=1;i<=n;++i) fa[i]=i;int cnt=0; for (int i=1;ix) continue; int xx=find(data[i].x),yy=find(data[i].y); if (xx!=yy){fa[xx]=yy;++cnt;} }if (cntx) continue; int xx=find(data[i].x),yy=find(data[i].y); if (xx!=yy){fa[xx]=yy;++cnt;} }if (cnt!=n-1) return 0;else return 1;}int main(){ //freopen("bzoj1196.in","r",stdin); n=read();k=read();m=read();int l=inf,r=0; for (int i=1;i>1; if (judge(mid)) r=mid-1;else l=mid+1; }printf("%d",l); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。