加载中...

winedia
• 博客等级：
• 博客积分：0
• 博客访问：82,447
• 关注人气：31
• 获赠金笔：0支
• 赠出金笔：0支
• 荣誉徽章：

HDU 5006 - Resistance 物理题 高斯消元

(2014-09-13 22:04:14)

高斯消元

［窝真的不想再用mac调程序了啊啊啊啊，简直高冷得太可怕了这系统，效率至少降低了一大半◡ ヽ(`Д´)ﾉ ┻━┻

#include
#include
#include
using namespace std;
#define N 500
int n,m,C,cnt;
int vis[N],q[N],ed[100010][2],p[N][N];
double A[N][N];
int br[10010],fa[10010];
void clear(){
memset(fa,0,sizeof fa);
memset(vis,0,sizeof vis);
memset(A,0,sizeof A);
memset(p,0,sizeof p);
for (int i = 1;i <= n;i ++) fa[i] = i;
C = 0;
cnt = 0;
}
int find(int x){return fa[x] == x ? x : (fa[x] = find(fa[x]));}
void merge(int u,int v){
int U = find(u);
int V = find(v);
if (U == V) return;
fa[U] = V;
}
void gauss(int n){
for (int i = 1;i <= n;i ++){
double tmp = A[i][i];
for (int j = i + 1;j <= n;j ++) if (A[j][i] < -1e-8 || A[j][i] > 1e-8){
double t = tmp / A[j][i];
for (int k = i;k <= n + 1;k ++){
A[j][k] = A[j][k] * t - A[i][k];
}
}
}
for (int i = n;i;i --){
if (A[i][i]<1e-8 && A[i][i] >-1e-8){
continue;
}
A[i][n + 1] = A[i][n + 1] / A[i][i];
double tmp = A[i][n + 1];
for (int j = i - 1;j;j --){
A[j][n + 1] -= A[j][i] * tmp;
A[j][i] = 0.0;
}
}
}
void bfs(int x){
int head = 0,tail = 0,now;
q[++ tail] = x;
vis[x] = 1;
memset(vis,0,sizeof vis);
for (int i = 1;i <= C;i ++) if (!vis[i] && p[now][i]) q[++ tail] = i,vis[i] = 1;
}
}
int main(){
int T;
int u,v,c,s,t;
scanf("%d",&T);
//cout << T << endl;
while (T --){
scanf("%d%d",&n,&m);
scanf("%d%d",&s,&t);
clear();
for (int i = 1;i <= m;i ++) {
scanf("%d%d%d",&u,&v,&c);
if (c) ed[cnt][0] = u,ed[cnt ++][1] = v;
else merge(u,v);
}
int a;
for (int i = 1;i <= n;i ++) {
a = find(i);
if (a == i) br[a] = ++ C;
}
if (fa[s] == fa[t]) {cout << "0.000000" << endl;continue;}
for (int i = 1;i <= cnt;i ++) {
u = ed[i][0],v = ed[i][1];
if (fa[u] != fa[v]) p[br[fa[u]]][br[fa[v]]] ++,p[br[fa[v]]][br[fa[u]]] ++;
}
bfs(br[fa[s]]);
if (!vis[br[fa[t]]]) {
printf("inf\n");
continue;
}
for (int i = 1;i <= C;i ++) {
if (i == br[fa[s]]) {A[i][i] = 1,A[i][C + 1] = 1.0;continue;}
if (i == br[fa[t]]) {A[i][i] = 1,A[i][C + 1] = 0.0;continue;}
for (int j = 1;j <= C;j ++) if (p[i][j] > 0) A[i][j] -= p[i][j],A[i][i] += p[i][j];
}
gauss(C);
int S = br[fa[s]];
double sumi = 0.0;
for (int i = 1;i <= C;i ++)if (p[S][i]) sumi += (1.0 - A[i][C + 1]) * p[S][i];
printf("%.6lf\n",1.0 / sumi);
}
return 0;
}

0

• 评论加载中，请稍候...

发评论

以上网友发言只代表其个人观点，不代表新浪网的观点或立场。

新浪BLOG意见反馈留言板　电话：4000520066 提示音后按1键（按当地市话标准计费）　欢迎批评指正

新浪公司 版权所有