[cogs386]电话网络

发表于 2016-11-07   |   分类于 二分  |  访问: 47 次

为了防止他们经常挂掉的域名

我搞了个二级域名解析到这个ip

题目在这

做法:

并查集判断联通

二分答案+宽搜

当然它可以让最大的p条边免费使用

所以我们需要一个used数组来记录

到达当前点还能使用的免费条数

也就是到达这个点以后我们还能使用多少条不合格的边

当然这个值越大越有利

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int _maxn=1010;
int n,m,p,head[_maxn],q[_maxn*_maxn],k,fa[_maxn],used[_maxn];
bool book[_maxn];
struct e{
	int to,dis,Next;
}edge[_maxn*22];
void add(int x,int y,int z){
	++k;
	edge[k].Next=head[x];
	edge[k].to=y;
	edge[k].dis=z;
	head[x]=k;
}
bool f(int x){
	memset(used,-1,sizeof(used));
	memset(book,false,sizeof(book));
	int he=1,tail=1,u,v;
	q[tail++]=1;
	used[1]=p;
	book[1]=true;
	while(he!=tail){
		u=q[he];
		for(int i=head[u];i;i=edge[i].Next){
			v=edge[i].to;
			if(edge[i].dis>x){
				if(used[u] && used[v]<used[u]-1){
					used[v]=used[u]-1;
					q[tail++]=v;
					if(!book[v])
						book[v]=true;
				}
			}
			else{
				if(used[v]<used[u]){
					used[v]=used[u];
					q[tail++]=v;
				}
				if(!book[v])
					book[v]=true;
			}
		}
		he++;
	}
	return book[n];
}
int find(int x){
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void uni(int x,int y){
	int u=find(x),v=find(y);
	if(u!=v)
		fa[u]=v;
}
int main(){
	freopen("phone.in","r",stdin);
	freopen("phone.out","w",stdout);
	scanf("%d%d%d",&n,&m,&p);
	int l=0,r=0,x,y,z;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
		uni(x,y);
		r=max(r,z);
	}
	if(find(1)!=find(n)){
		printf("-1\n");
		return 0;
	}
	int mid;
	while(l<r){
		mid=(l+r)>>1;
		if(f(mid))	r=mid;
		else		l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}

 

发表新评论

© 2017 Powered by Typecho & Theme Quark