【二分+最小树形图】UVA11865 比赛网络
Description
During 2009 and 2010 ICPC world finals, the contest was webcasted via world wide web. Seeing this, some contest organizers from Ajobdesh decided that, they will provide a live stream of their contests to every university in Ajobdesh. The organizers have decided that, they will provide best possible service to them. But there are two problems: 1. There is no existing network between universities. So, they need to build a new network. However, the maximum amount they can spend on building the network is C. 2. Each link in the network has a bandwidth. If, the stream’s bandwidth exceeds any of the link’s available bandwidth, the viewers, connected through that link can’t view the stream. Due to the protocols used for streaming, a viewer can receive stream from exactly one other user (or the server, where the contest is organized). That is, if you have two 128kbps links, you won’t get 256kbps bandwidth, although, if you have a stream of 128kbps, you can stream to any number of users at that bandwidth. Given C, you have to maximize the minimum bandwidth to any user.
Solution
二分最小带宽,求最小树形图看是否超过C。
Code
写这题各种犯逗,简直感动不能多说。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=,maxm=1e4+; struct edge{
int v,u,b,c;
bool operator<(const edge&a)
const{return b<a.b;}
}E[maxm],e[maxm];
int in[maxn],pre[maxn],vis[maxn],id[maxn];
int N,M,C; int work(int n,int m,int lim){
memcpy(e,E,sizeof(e));
long long ret=;
int root=;
if(!lim) lim=; while(){
memset(in,,sizeof(in));
int inf=in[];
for(int i=lim;i<=m;i++){
int u=e[i].u,v=e[i].v;
if(u!=v&&e[i].c<in[v]){
in[v]=e[i].c;
pre[v]=u;
}
}
for(int i=;i<=n;i++)
if(i!=root&&in[i]==inf) return ; in[root]=;
int cnt=;
memset(id,,sizeof(id));
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++){
ret+=in[i];
if(!vis[i]){
int u=i;
while(u!=root&&!vis[u]){
vis[u]=i;
u=pre[u];
}
if(vis[u]==i){
++cnt;
int v=u;
do{
id[v]=cnt;
v=pre[v];
}while(v!=u);
}
}
} if(!cnt) break;
for(int i=;i<=n;i++)
if(!id[i]) id[i]=++cnt;
for(int i=lim;i<=m;i++){
int v=e[i].v;
e[i].u=id[e[i].u];
e[i].v=id[e[i].v];
if(e[i].u!=e[i].v)
e[i].c-=in[v];
}
n=cnt;
root=id[root];
}
if(ret<=C) return ;
return ;
} int main(){
int T;
scanf("%d",&T); while(T--){
scanf("%d%d%d",&N,&M,&C);
for(int i=;i<=M;i++){
scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].b,&E[i].c);
E[i].u++,E[i].v++;
}
sort(E+,E+M+); int l=,r=M;
while(l<r){
int mid=(l+r+)>>;
if(work(N,M,mid)) l=mid;
else r=mid-;
} if(!l) printf("streaming not possible.\n");
else printf("%d kbps\n",E[l].b);
}
return ;
}
最新文章
- 设置MYSQL允许用IP访问
- debian和ubuntu的sh dash bash
- HTTP基础03--HTTP报文
- C语言中时间调用处理的相关函数介绍
- XNA Game Studio 4.0 Programming 随便读,随便记 &ldquo;Rendering Text&rdquo;
- FCLK PCLK HCLK
- NFC学习笔记2——Libnfc简介及安装
- ruby将mysql查询到的数据保存到excel
- servlet(2)servlet过滤器
- C# 中使用面向切面编程(AOP)中实践代码整洁
- IT java培训机构名单(不全)
- vue 拖拽移动(类似于iPhone虚拟home )
- fiddler抓包工具总结
- Codeforces Round #453 (Div. 1) D. Weighting a Tree(构造)
- matlab中变量问题——readonly 索引超出矩阵维度 workspacefunc 215
- Mysql自增ID起始值修改
- Win2012&;Win2008双系统启动菜单设置
- Bloom Filter解析
- 数组名和数组名取地址&;
- ajax json用法 上传文件 登录