上海装修网站大全,潍坊网站建设公司电话,青岛公交优化,wordpress热门文章 图片嘟嘟嘟 一看到异或#xff0c;就想到按位处理#xff0e; 当处理到第\(i\)位的时候#xff0c;\(f[u]\)表示节点\(u\)到\(n\)的路径#xff0c;这一位为\(1\)的期望#xff0c;那么为\(0\)就是\(1 - f[u]\)#xff0c;于是有\[f[u] \frac{1}{d[u]} (\sum _ {v \in V, w … 嘟嘟嘟 一看到异或就想到按位处理 当处理到第\(i\)位的时候\(f[u]\)表示节点\(u\)到\(n\)的路径这一位为\(1\)的期望那么为\(0\)就是\(1 - f[u]\)于是有\[f[u] \frac{1}{d[u]} (\sum _ {v \in V, w 0} f[v] \sum _ {v \in V, w 1} 1 - f[v])\] 因为是异或所以如果边权这一位是0的话应该加上\(f[v]\)否则加上\(1 - f[v]\)。 然后整理一下\[d[u] * f[u] - \sum _ {v \in V, w 0} f[v] \sum _ {v \in V, w 1} f[v] \sum _ {v \in V, w 1} 1\] 于是就可以高斯消元了。 答案为\(\sum 2 ^ i * ans_i[1]\)。 需要注意的是,重边只应该加一次,对应的度数也应该只加\(1\)。 #includecstdio
#includeiostream
#includecmath
#includealgorithm
#includecstring
#includecstdlib
#includecctype
#includevector
#includestack
#includequeue
using namespace std;
#define enter puts()
#define space putchar( )
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF 0x3f3f3f3f;
const db eps 1e-8;
const int maxn 105;
const int maxe 2e4 5;
inline ll read()
{ll ans 0;char ch getchar(), last ;while(!isdigit(ch)) last ch, ch getchar();while(isdigit(ch)) ans (ans 1) (ans 3) ch - 0, ch getchar();if(last -) ans -ans;return ans;
}
inline void write(ll x)
{if(x 0) x -x, putchar(-);if(x 10) write(x / 10);putchar(x % 10 0);
}int n, m, Max 0;
int du[maxn];
struct Edge
{int nxt, to, w;
}e[maxe];
int head[maxn], ecnt -1;
void addEdge(int x, int y, int w)
{e[ecnt] (Edge){head[x], y, w};head[x] ecnt;
}db f[maxn][maxn], ans[maxn], Ans 0;
void build(int x)
{Mem(f, 0);for(int i 1; i n; i) //小于n{f[i][i] du[i];for(int j head[i]; j ! -1; j e[j].nxt)if((e[j].w x) 1) f[i][e[j].to], f[i][n 1];else --f[i][e[j].to];}
}
db Gauss()
{for(int i 1; i n; i){int pos i;for(int j i 1; j n; j)if(fabs(f[j][i]) fabs(f[pos][i])) pos j;if(pos ! i) swap(f[i], f[pos]);db tp f[i][i];if(fabs(tp) eps) for(int j i; j n 1; j) f[i][j] / tp;for(int j i 1; j n; j){db tp f[j][i];for(int k i; k n 1; k) f[j][k] - tp * f[i][k];}}for(int i n; i; --i){ans[i] f[i][n 1];for(int j i - 1; j; --j) f[j][n 1] - f[j][i] * f[i][n 1];}return ans[1];
}int main()
{Mem(head, -1);n read(); m read();for(int i 1; i m; i){int x read(), y read(), w read();addEdge(x, y, w); du[x];if(x ^ y) addEdge(y, x, w), du[y];Max max(Max, w);}for(int i 0; (1 i) Max; i)build(i), Ans Gauss() * (1 i);printf(%.3lf\n, Ans);return 0;
} 转载于:https://www.cnblogs.com/mrclr/p/10137454.html
