uva 12587 二分枚举

思路:维护一个森林,二分枚举最小的最大值。

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define Maxn 20010
#define Maxm 40010
#define LL long long
#define Abs(x) ((x)>0?(x):(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define inf 1e15
#define lowbit(x) (x&(-x))
#define clr(x,y) memset(x,y,sizeof(x))
#define Mod 1000000007
using namespace std;
int head[Maxn],vi[Maxn],dfn[Maxn],low[Maxn],num[Maxn],is[Maxn],Stack[Maxn],top,e,lab;
int n,m;
LL val[Maxn],need[Maxn],cnt;
struct Edge{
int u,v,next,f;
LL val;
}edge[Maxm];
void init()
{
clr(head,-);
clr(vi,);
clr(is,);
clr(need,);
clr(dfn,);
clr(low,);
clr(num,);
e=lab=cnt=;
}
void add(int u,int v,LL val)
{
//cout<<u<<" "<<v<<endl;
edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].f=,edge[e].next=head[u],head[u]=e++;
}
void Tarjan(int u)
{
int i,v,cc;
++cnt;
vi[u]=;
dfn[u]=low[u]=++lab;
Stack[++top]=u;
for(i=head[u];i!=-;i=edge[i].next){
v=edge[i].v;
if(edge[i].f) continue;
edge[i].f=edge[i^].f=;
if(!dfn[v]){
cc=cnt;
Tarjan(v);
if(low[v]>dfn[u]){
is[u]=;
num[v]=cnt-cc;
}
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],dfn[v]);
}
}
bool dfs(int u,LL nal)
{
int i,v;
need[u]=val[u];
vi[u]=;
for(i=head[u];i!=-;i=edge[i].next){
v=edge[i].v;
if(vi[v]) continue;
if(!dfs(v,nal))
return false;
if(is[u]){
if(num[v]*(cnt-num[v])*edge[i].val+need[v]>nal)
need[u]+=num[v]*(cnt-num[v])*edge[i].val;
}
if(need[u]>nal)
return false;
}
return true;
}
bool OK(LL x,int p)
{
int i,j;
for(i=;i<=top;i++) vi[Stack[i]]=;
for(i=;i<=top;i++) if(val[Stack[i]]>x){
return false;
}
if(!dfs(p,x))
return false;
return true;
}
void solve()
{
int i,j;
LL ans=;
for(i=;i<=n;i++) if(!dfn[i]){
Tarjan(i);
LL l,r,mid;
l=,r=inf;
while(l<r){
mid=(l+r)>>;
if(OK(mid,i))
r=mid;
else
l=mid+;
}
ans=max(l,ans);
cnt=;
top=;
}
printf("%lld\n",ans);
return ;
}
int main()
{
int i,j,u,v,t,Ca=;
LL cc;
scanf("%d",&t);
while(t--){
init();
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
scanf("%lld",val+i);
for(i=;i<=m;i++){
scanf("%d%d%lld",&u,&v,&cc);
add(u,v,cc);
add(v,u,cc);
}
printf("Case %d: ",++Ca);
solve();
}
return ;
}
上一篇:Python For 循环


下一篇:java 里面的string 和byte[] 怎么互转