710官方网站N 号节点甘休,N 号节点停止

Description

给定贰个无向连通图,其节点编号为 一 到
N,其边的权值为非负整数。试求出一条从 壹 号节点到 N
号节点的门路,使得该路线上经过的边的权值的“XOTiguan和”最大。该路线能够重新经过有个别节点或边,当一条边在路线中出现数次时,其权值在盘算“XOTiguan和”时也要被再一次总括相应多的次数。

一向求解上述难题相比辛苦,于是你决定使用非完美算法。具体来说,从 1号节点起先,以相当于的可能率,随机接纳与方今节点相关联的某条边,并沿那条边走到下二个节点,重复那些进程,直到走到
N 号节点截止,便取得一条从 1 号节点到 N
号节点的不2法门。明显赢得每条那样的途径的可能率是区别的还要每条那样的路径的“XOTiggo和”也不一样。未来请你求出该算法获得的门路的“XO昂科拉 和”的期望值。

  

Description

给定二个无向连通图,其节点编号为 壹 到
N,其边的权值为非负整数。试求出一条从 一 号节点到 N
号节点的路子,使得该路线上通过的边的权值的“XO奇骏和”最大。该路线能够另行经过有些节点或边,当一条边在途径中冒出反复时,其权值在估测计算“XOHaval和”时也要被再一次计算相应多的次数。
直接求解上述难题比较困难,于是你控制动用非完美算法。具体来说,从 一号节点开端,以也正是的可能率,随机挑选与当前节点相关联的某条边,并沿那条边走到下2个节点,重复这一个历程,直到走到
N 号节点结束,便取得一条从 1 号节点到 N
号节点的门径。显著赢得每条那样的门径的票房价值是例外的还要每条这样的门路的“XO中华V和”也不等同。今后请你求出该算法得到的路线的“XO奥迪Q伍 和”的期望值。

Input

从文件input.txt中读入数据,输入文件的率先行是用空格隔断的多个正整数N和M,分别代表该图的节点数和边数。紧接着的M行,每行是用空格隔开分离的四个非负整数u,v和w(一≤u,v≤N,0≤w≤10九),表示该图的一条边(u,v),其权值为w。输入的多少有限帮忙图连通,十分三的多少满意N≤30,百分百的多寡满意二≤N≤100,M≤10000,可是图中或许有重边或自环。

Time Limit: 1000 ms   Memory Limit: 256 MB

solution

正解:高斯消元
据书上说期望的线性性,必要的事物可以拆成每1位二进制位的希望之和
思量从i到达n时该2进制位为1的方案,分边权是不是为一切磋:
\(f[j]+=f[i]/du[i]\)
假如边权该位为0
\(f[j]+=(1-f[i])/du[i]\)
倘诺边权的该位为①
思量到那是有向图,且存在环,所以无法拓扑序DP,用高斯消元能够解:
我们把
f[1],f[2]…f[n]作为是变量,然后du[i]作为是周全,就足以求了
然则做出来是WA的?一看题解就像必要求逆向推啊?原因就好像是正推会存在不能够走到i的概率?

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=105,M=20005;
int n,m,num=0,du[N],head[M],to[M],dis[M],nxt[M];
void link(int x,int y,int z){
    nxt[++num]=head[x];to[num]=y;head[x]=num;dis[num]=z;}
double a[N][N],ans=0;
inline double solve(){
    for(int l=1;l<=n;l++){
        int maxid=l;
        for(int i=l+1;i<=n;i++)
            if(fabs(a[i][l])>fabs(a[maxid][l]))maxid=l;
        if(l!=maxid)swap(a[l],a[maxid]);
        for(int i=l+1;i<=n;i++){
            if(!a[i][l])continue;
            double tmp=a[l][l]/a[i][l];
            for(int j=l;j<=n+1;j++)
                a[i][j]=a[l][j]-tmp*a[i][j];
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=i+1;j<=n;j++)
            a[i][n+1]-=a[i][j]*a[j][n+1];
        a[i][n+1]/=a[i][i];
    }
    return a[1][n+1];
}
void work()
{
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        link(x,y,z);du[y]++;
        if(x!=y)link(y,x,z),du[x]++;
    }
    for(int w=0;w<=30;w++){
        memset(a,0,sizeof(a));
        for(int i=1;i<n;i++){
            a[i][i]=1.0;
            for(int j=head[i];j;j=nxt[j]){
                int u=to[j];
                if(dis[j]&(1<<w))
                    a[i][u]+=1.0/du[i],a[i][n+1]+=1.0/du[i];
                else a[i][u]-=1.0/du[i];
            }
        }
        a[n][n]=1.0;
        ans+=solve()*(1<<w);
    }
    printf("%.3lf\n",ans);
}

int main(){
    work();
    return 0;
}

Output

出口文件 output.txt 仅包括三个实数,表示上述算法获得的不二等秘书诀的“XO宝马X伍和”的想望值,必要保留四人小数。(提议使用精度较高的数据类型实行测算)

Description

  给定一张N个点、M条边的无向图 $G$
。每一种点有个权值Wi。

  咱们定义 $G_i$ 为图 $G$ 中删除第 $i$
号顶点后的图。大家想总结 $G_1, G_2, …, G_n$
那N张图的权值。

  对于自由一张图 $G$
,它的权值是那样定义的:

  一.
假使 $G$ 是联通图,那么 $G$ 的权值为 $G$
中存有终端权值的乘积。

  2.
只要 $G$ 是非联通图,那么 $G$ 的权值为 $G$
中全体联通块的权值之和。

  $G$
中的2个联通块指的是 $G$
的四个子图,并且那些子图中的点两两相连(包含直接连接恐怕直接连接),并且不设有子图外的点使得子图内的点能与子图外的点相连。

Sample Input

2 2
1 1 2
1 2 3

Input

  第2行李包裹罗七个整数 $n$ 和 $m$ $(贰
\le n \le 10^5, 1 \le m \le 2 \times 10^伍)$
,分别代表点数和边数。

  第贰行李包裹括 $n$ 个整数 $w_1, w_2,
…, w_n$ $(1 \le w_i \le 拾^九)$, 表示每一种终端的权值。

  接下去 m 行,每行多个整数 $x_i$ 和
$y_i$ $(1 \le x_i, y_i \le n, x_i \ne y_i)$,
表示一条无向边。

  输出只有四个平头: $S =
(\sum\limits_{i=1}^{n}i\cdot z_i) \text{ mod } (10^9 + 7)$, 其中
$z_i$ 是图 $G_i$ 的权值。

 

Sample Input

Sample Output

10 3
3 3 3
2 3 3 
2 3 1 
3 1 1 
3 1 2 
1 3 1 
1 1 2 
1 2 2 
1 3 2 
1 2 1
3
1
3
0
1
0
1
0
0
1

 

 

Sample Output

2.333

Hint 

  【数据范围及约定】

  子任务1(5分): $n \leq 10, m \leq
20$

  子任务2(10分): $n \leq 1000, m
\leq 2000$

  子职分三(十八分): 该图恰为1棵树,$m
= n-壹$

  子职责四(1八分):
该图为一幅联通图

  子职责5(四十多分):
大家会拿最强的数量来测验评定你的程序(mmp)

  对于有所数据,$二 \le n \le 10^5, 1
\le m \le 2 \times 10^5$

 


 

HINT

样例解释:有11分之伍的票房价值直接从一号节点走到2号节点,该路线的“XO卡宴和”为叁;有四分之一的可能率从一号节点走三回一号节点的自环后走到贰号节点,该路线的“XORubicon和”为一;有1/8的概率从一号节点走四次一号节点的自环后走到贰号节点,该路线的“XOHummerH二和”为三;„„;依此类推,可见“XORAV四和”的期望值为:3/二+百分之二十五+3/八+1/1陆+3/3贰+„„=7/3,相当于二.333。

转载自Navi_Awson巨佬%%%%%oTTTTTTTTTZ

http://www.cnblogs.com/NaVi-Awson/p/7707368.html

首先观望路径$xor$值,仍然选择按位做。

我们设$f_u$代表从$u$到$n$的路径异或值为$一$的票房价值。分明$f_n
== 0$。

此外,设$w(u,
v)$为$u->v$的边权($1/0$),那么有:

$$f_u = \sum_{(u,v) \in E,\ w(u,v)
= 0} \frac{f_v}{degree_u} + \sum_{(u,v) \in E,\ w(u,v) = 1}
\frac{1-f_v}{degree_u}$$

那么大家得以博得$n$个方程,用高斯消元求解。

能够乘上$degree_u$减小引用误差。

那题尤其说美赞臣(Meadjohnson)下怎么不可能顺推而要逆推:

很多题解的传教是因为“要是正推的话,$壹−f_i$代表的不但从$一$到$i$异或和不为$①$的概率,还富含了从$一$不走到$i$的票房价值,不能够变换”。

倘使如此表明,那就解释不了$i$走不到$n$的事态。

本人以为合理的解答是:因为$一$能够重复走多次,而$n$只好走$壹$次。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 struct Node
 8 {
 9     int next,to;
10     int dis;
11 }edge[20005];
12 double a[105][105],ans;
13 int n,m,head[105],num,d[105];
14 int pw[31];
15 void add(int u,int v,int dis)
16 {
17     num++;
18     edge[num].next=head[u];
19     head[u]=num;
20     edge[num].to=v;
21     edge[num].dis=dis;
22 }
23 void gauss()
24 {int i,j,now,k;
25   for (i=1;i<=n;i++)
26     {
27       now=i;
28       for (j=i+1;j<=n;j++)
29         if (fabs(a[now][i])<fabs(a[j][i]))
30       now=j;
31       for (j=i;j<=n+1;j++)
32         swap(a[now][j],a[i][j]);
33       for (j=i+1;j<=n+1;j++)
34         a[i][j]/=a[i][i];
35           a[i][i]=1;
36       for (j=i+1;j<=n;j++)
37         {
38           for (k=i+1;k<=n+1;k++)
39         a[j][k]-=a[i][k]*a[j][i];
40           a[j][i]=0;
41         }
42     }
43   for (i=n;i>=1;i--)
44     {
45       for (j=i+1;j<=n;j++)
46         {
47           a[i][n+1]-=a[i][j]*a[j][n+1];
48         a[i][j]=0;
49         }
50           a[i][n+1]/=a[i][i];
51           a[i][i]=1;
52     }
53 }
54 int main()
55 {int i,j,u,v,w;
56     cin>>n>>m;
57     pw[0]=1;
58     for (i=1;i<=30;i++)
59     pw[i]=pw[i-1]*2;
60     for (i=1;i<=m;i++)
61     {
62         scanf("%d%d%d",&u,&v,&w);
63         add(u,v,w);
64         d[v]++;
65         if (u!=v) add(v,u,w),d[u]++;
66     }
67     for (i=0;i<=30;i++)
68     {
69         memset(a,0,sizeof(a));
70         for (u=1;u<n;u++)
71         {
72             a[u][u]=d[u];
73             for (j=head[u];j;j=edge[j].next)
74             {
75                 int v=edge[j].to;
76                 if (edge[j].dis&pw[i]) a[u][v]++,a[u][n+1]++;
77                 else a[u][v]--;
78             }
79         }
80         a[n][n]=1;
81         gauss();
82         ans+=a[1][n+1]*(double)pw[i];
83     }
84     printf("%.3lf\n",ans);
85 }

 

题解

   style=”font-size: 1陆px;”>未有何样能阻碍笔者把Tarjan打残。

  标题涉及到删点操作。

  要是删的点$u$是叁个非割顶,那么它的消解貌似对那么些联通块完整未有太大的熏陶,要拍卖的话可是是该当前联通块的权值$val$除去$u$的权值$w_u$。

  借使删的点$u$是3个割顶,那么它会将那些联通块分成若干局地,具体就是在Tarjan的缩点树上,把子树全体断开,把老爹也断开。难点来了,割顶那一个东西很烦怎么处理?

 

转树

  割顶出现了!它可以同时处于七个点双内,mmp

  对于种种点双,大家临时新建三个代表点,将点双内的全数点连向那个代表点。那样,三个割顶可以被再三再四到多个点双的代表点,同时全部图转成了树的模样。

  710官方网站 1

  那么断开二个割顶$u$会潜移默化到什么样区块,就一目掌握了,即那种树上,$u$的拥有子树和阿爸那2只的有个别。

  发现那实则同化了断开非割顶的操作,非割顶永远地处根节点或叶子节点,其实本质上拍卖是同等的。

  维护

  $$f_u=\prod\limits_{v\in
以u为根的树}w[v]\\g_u=\sum\limits_{v是u的子树}f[v]$$

  则删去3个点$u$,对中国人民解放军第5野战军联通块权值$val$的影响即为:

  $$val=\frac{val}{f_u}+g_u$$

    即老爹那两头的权值+全部子树的权值和

 

小细节与特判

  一.甩卖删去割顶的时候(即上边包车型客车尾声3个公式),$\frac{val}{f_u}$希望拿到的是阿爸那1只的权值,但1旦$u$是树的根,那玩意儿弄出来却是1,而不是大家期望的0(坑爹),所以记录一下大家要处理的割顶是或不是八个树的根,特判一下。

  
 二.Tarjan深搜的初阶点要记为割顶。

 


 

710官方网站 2710官方网站 3

 1 #include <cstdio>
 2 #define min(a,b) (a<b?a:b)
 3 using namespace std;
 4 typedef long long ll;
 5 const ll N=200010,Mod=1e9+7;
 6 int n,m,h1[N],h2[N*2],tot;
 7 int col[N],colcnt,st[N],top,bcnt,head[N];
 8 ll info[N],sumup,ans,f[N*2],g[N*2],w[N*2];
 9 int dfn[N],low[N],ins[N],tmcnt;
10 bool cut[N];
11 struct Edge{int v,next;}G[N*6];
12 inline void addEdge(int u,int v,int *h){
13     G[++tot].v=v; G[tot].next=h[u]; h[u]=tot;
14 }
15 void tarjan(int u,int fa){
16     st[++top]=u;
17     ins[u]=1;
18     dfn[u]=low[u]=++tmcnt;
19     col[u]=colcnt;
20     info[col[u]]=(info[col[u]]*w[u])%Mod;
21     for(int i=h1[u],v,ccnt=0;i;i=G[i].next)
22     if((v=G[i].v)!=fa){
23         if(!ins[v]){
24             ccnt++;
25             tarjan(v,u);
26             low[u]=min(low[u],low[v]);
27             if((!fa&&ccnt>1)||(fa&&dfn[u]<=low[v]))
28                 cut[u]=1;
29             if(dfn[u]<=low[v]){
30                 w[(++bcnt)+n]=1;
31                 do{
32                     addEdge(st[top],bcnt+n,h2);
33                     addEdge(bcnt+n,st[top],h2);
34                     top--;
35                 }while(st[top+1]!=v);
36                 addEdge(u,bcnt+n,h2);
37                 addEdge(bcnt+n,u,h2);
38             }
39         }
40         else if(ins[v]==1)
41             low[u]=min(low[u],dfn[v]);
42     }
43     ins[u]=2;
44 }            
45 void dfs(int u,int fa){
46     f[u]=w[u]; g[u]=0;
47     for(int i=h2[u],v;i;i=G[i].next)
48         if((v=G[i].v)!=fa){
49             dfs(v,u);
50             f[u]=(f[u]*f[v])%Mod;
51             g[u]=(g[u]+f[v])%Mod;
52         }
53 }
54 ll ksm(ll bas,ll tm){
55     if(tm==0) return 1;
56     ll ret=ksm(bas,tm/2);
57     ret=(ret*ret)%Mod;
58     return ((tm&1)?ret*bas:ret)%Mod;
59 }
60 ll inv(int x){return ksm(x,Mod-2);}
61 int main(){
62     scanf("%d%d",&n,&m);
63     for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
64     for(int i=1,u,v;i<=m;i++){
65         scanf("%d%d",&u,&v);
66         addEdge(u,v,h1); addEdge(v,u,h1);
67     }
68     for(int i=1;i<=n;i++)
69         if(!dfn[i]){
70             info[++colcnt]=1;
71             tarjan(i,0);
72             cut[i]=1;
73             sumup=(sumup+info[colcnt])%Mod;
74             head[colcnt]=i;
75             dfs(i,0);
76         }
77     for(ll i=1,k;i<=n;i++){
78         int c=col[i];
79         if(!cut[i])
80             k=(sumup+Mod*2-info[c]+(info[c]*inv(w[i]))%Mod)%Mod;
81         else{
82             if(head[c]!=i) k=(sumup+Mod*2-info[c]+(info[c]*inv((f[i])%Mod)%Mod)%Mod+g[i])%Mod;
83             else k=(sumup+Mod*2-info[c]+g[i])%Mod;
84         }
85         ans=(ans+(i*k)%Mod)%Mod;
86     }
87     printf("%lld\n",ans);
88     return 0;
89 }

奇妙代码

 

相关文章