注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

ctsc2012 circuit  

2014-03-03 11:51:52|  分类: ctsc |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
跷课来补了一发……
极力推荐liou_zhou101的题解……以我这种物理都能看懂可见liou_zhou101能成为非常优秀的物理老师……大赞
http://hi.baidu.com/liouzhou_101/item/46e7c9584fbd1805aaf6d7f9

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#define maxn 50010
#define maxm 100010
using namespace std;
const double R=10000;
int n,m,deg[maxn],father[maxn];
int nEdge=1,to[maxm],next[maxm],start[maxn];
double K[maxn],B[maxn],U[maxn];
void make(int a,int b)
{
++nEdge,to[nEdge]=b,next[nEdge]=start[a],start[a]=nEdge;
}
void update(int a)
{
if(deg[a]==1)
K[a]=0.5,B[a]=-0.5*U[a];
else
{
double sum1=deg[a],sum2=-U[a];
for(int j=start[a];j;j=next[j])
if(to[j]!=father[a])
sum1=sum1-K[to[j]],sum2=sum2+U[to[j]]+B[to[j]];
K[a]=1.0/sum1,B[a]=sum2/sum1;
}
}
double phi(int p)
{
if(p==n)
return 0;
return phi(father[p])*K[p]+B[p];
}
void BFS(int p)
{
static bool use[maxn];
static int queue[maxn];
int front=0,rear=1;
queue[rear]=p,use[p]=true;
while(front<rear)
{
int p=queue[++front];
for(int i=start[p];i;i=next[i])
if(use[to[i]]==false)
{
queue[++rear]=to[i];
use[to[i]]=true;
father[to[i]]=p;
}
}
for(int i=n;i>1;--i)
update(queue[i]);
}
void read()
{
scanf("%d %d",&n,&m);
for(int i=2,a,b;i<=n;++i)
{
scanf("%d %d",&a,&b);
++deg[a],++deg[b];
make(a,b),make(b,a);
}
int leaf;
for(leaf=1;deg[leaf]!=1;++leaf);
++n,make(n,leaf),make(leaf,n),++deg[leaf];
BFS(n);
}
void Query()
{
char c;
for(int i=1,u,v,w;i<=m;++i)
{
for(c=getchar();!isalpha(c);c=getchar());
if(c=='C')
{
scanf("%d %d %d",&u,&v,&w);
if(u==father[v])
swap(u,v),w*=-1;
U[u]+=w;
for(int j=u;j;j=father[j])
update(j);
}
if(c=='Q')
{
scanf("%d",&u);
printf("%.10f\n",phi(u));
}
}
}
int main()
{
freopen("circuit.in","r",stdin);
freopen("circuit.out","w",stdout);
read();
Query();
fclose(stdin);
fclose(stdout);
return 0;
}

  评论这张
 
阅读(431)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017