Floyd-Warshall算法原理及实现
概述 Floyd-Warshall算法,或者简称为Floyd算法,是一种方便好写的全图最短 …
May all the beauty be blessed.
晶体具有自范性,有固定的熔沸点。单晶体具有各向异性(高中化学中的晶体一般都是单晶体)。
非晶体没有自范性,没有固定的熔沸点,具有各向同性。
晶体和非晶体的根本区别:基本构成微粒是否按一定规律周期性重复排列。
1.原子晶体
由原子组成的晶体,微粒间作用力为共价键。
常见晶体:$Si、SiO_2、Si_3N_4、BN$
2.分子晶体
由分子组成的晶体,微粒间作用力为范德华力、氢键等分子间作用力。
大多数非金属单质、大多数有机物、几乎所有的酸、所有非金属氢化物、(常温常压下的)各种气体都是分子晶体。
常见晶体:$Cl_2$、$He$、$HCl$
3.离子晶体
由离子组成的晶体,微粒间作用力为离子键。
金属氧化物、强碱、绝大多数盐是离子晶体。
4.金属晶体
包括金属、合金,微粒间作用力为金属键。
一般来说,原子晶体>离子晶体>分子晶体。金属晶体熔沸点差别较大。
特殊情况举例:$MgO$是离子晶体,但其熔点(约2800℃)高于部分原子晶体。
1.原子晶体:比较共价键强弱
即比较共价键的键能。一般情况下,原子半径越小,键长越短,键能越大,晶体熔沸点越高。
如 $C>SiC>Si$
2.分子晶体:比较分子间作用力大小
①一般情况下,对于组成和结构相似的晶体,相对分子质量越大,范德华力越大,熔沸点越高。
如 $HI>HBr>HCl$
②相对分子质量相近时,极性分子范德华力大,熔沸点高。
如 $CO>N_2$
③含氢键的分子熔沸点高,且氢键越多熔沸点越高。
如 $H_2O>HF>NH_3$
3.离子晶体:比较离子键强弱
晶格能:气态离子形成1mol离子晶体释放的能量。离子带电荷越多,半径越小,晶格能越大。
一般情况下,晶格能越大,离子键越强,熔沸点越高。
如 $KF>KCl>KBr>KI$
4.金属晶体:比较金属键强弱
遵循公式:$F = \frac{kq_1q_2}{r^2}$(q为价电子)
金属原子价电子越多,半径越小,金属件越强,熔沸点越高。
如 $Al>Mg>Na$
1.“熔沸点”和“稳定性”没有必然关系,如H2O的沸点高于HF,但HF热稳定性更好(取决于非金属性强弱)。
由于博主高考完了,本文不再更新。
题目地址:洛谷:【P3232】[HNOI2013]游走 – 洛谷、BZOJ:Problem 3143. — [Hnoi2013]游走
一个无向连通图,顶点从1编号到N,边从1编号到M。 小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。
输入格式:
第一行是正整数N和M,分别表示该图的顶点数 和边数,接下来M行每行是整数u,v(1<=u,v<=N),表示顶点u与顶点v之间存在一条边。
输入保证30%的数据满足N<=10,100%的数据满足2<=N<=500且是一个无向简单连通图。
输出格式:
仅包含一个实数,表示最小的期望值,保留3位小数。
输入样例#1:
3 3 2 3 1 2 1 3
输出样例#1:
3.333
边(1,2)编号为1,边(1,3)编号2,边(2,3)编号为3。
显然,如果我们知道经过每一条边的期望经过次数,那么贪心地按期望从大到小安排编号就好了。考虑如何求经过边的期望,边$(u, v)$的期望$\mathrm{E}(u, v)$是
$$ \mathrm{E}(u, v) = \frac{\mathrm{E}(u)}{deg_u} + \frac{\mathrm{E}(v)}{deg_v} $$
其中$deg_u$表示$u$的度数。我们把问题转化成如何求经过$u$点的期望$\mathrm{E}(u)$了。
这里我们考虑使用高斯消元解方程组的思路求解,对于每一个点,可以列出如下方程
$$ \mathrm{E}(u) = \sum_{(u, v) \in G, v \neq n} \frac{\mathrm{E}(v)}{deg_v} $$
移项后即可得到适合高斯消元的式子。对于$1$点,令高消方程的等号右边为$1$即可,这是让$1$强制至少经过1次。
复杂度$O(n^3)$。
// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <functional>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
return res * neg;
}
inline char readsingle() {
register char c;
while(!isgraph(c = fgc())) {}
return c;
}
const int MAXN = 505;
int n, m, deg[MAXN];
double mat[MAXN][MAXN];
inline void gauss() {
for(int i = 1; i < n; i++) {
int k = i;
for(int j = i + 1; j < n; j++) {
if(fabs(mat[k][i]) < fabs(mat[j][i])) k = j;
}
if(k != i) {
for(int j = 1; j < n + 1; j++) {
std::swap(mat[k][j], mat[i][j]);
}
}
for(int j = 1; j < n; j++) {
if(j == i) continue;
double r = mat[j][i] / mat[i][i];
for(int k = 1; k < n + 1; k++) {
mat[j][k] -= r * mat[i][k];
}
}
}
for(int i = 1; i < n; i++) mat[i][n] /= mat[i][i];
}
std::vector<int> gra[MAXN];
struct Edge {
int u, v;
double prob;
inline bool operator>(const Edge &rhs) const {
return prob > rhs.prob;
}
} edges[MAXN * MAXN];
int main() {
n = readint(); m = readint();
for(int i = 1, u, v; i <= m; i++) {
u = readint(); v = readint();
deg[u]++; deg[v]++;
edges[i] = Edge {u, v};
gra[u].push_back(v); gra[v].push_back(u);
}
for(int i = 1; i < n; i++) {
mat[i][i] = 1;
for(int j = 0; j < gra[i].size(); j++) {
int v = gra[i][j];
if(v == n) continue;
mat[i][v] = -1.0 / deg[v];
}
}
mat[1][n] = 1;
gauss();
for(int i = 1; i <= m; i++) {
edges[i].prob = mat[edges[i].u][n] / deg[edges[i].u] + mat[edges[i].v][n] / deg[edges[i].v];
}
std::sort(edges + 1, edges + m + 1, std::greater<Edge>());
double ans = 0;
for(int i = 1; i <= m; i++) {
ans += i * edges[i].prob;
}
printf("%.3lf", ans);
return 0;
}