rt,P6030,关O2,RE65,开O2,WA95 应该是UB了,但是找不到,求助
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#pragma GCC optimeze(3)
#pragma GCC optimeze(2)
#define PII pair<int, int>
#define pb push_back
#define fi first
#define se second
#define lowbit(x) (x & (-x))
using namespace std;
const int N=2e6+5;
const int M=2e6+5;
const int mod=1e9+7;
double eps=1e-7;
int n,m,s,t,dfc,dfn[N],low[N],deg[N],be[N],cnt,id[N],vis[N];
vector<int>G[N],scc[N];
double a[205][205], ans[205],f[N];
stack<int>S;
bool swapline(int r, int c) {
int maxr = r;
for (int i = r + 1; i <= n; i++)
if (fabs(a[i][c]) > fabs(a[maxr][c]))maxr = i;
if (fabs(a[maxr][c]) < eps)return 0;
swap(a[maxr],a[r]);
return 1;
}
int Gauss(int on) {
int r = 1;
for (int c = 1; c <= on; c++) {
if (!swapline(r, c))continue;
for (int i = r + 1; i <= on; i++) {
double t = a[i][c] / a[r][c];
for (int j = 1; j <= on + 1; j++)a[i][j]-=t*a[r][j];
}
r++;
}
r--;
if (r < on) {
for (int i = r + 1; i <= on; i++)
if (fabs(a[i][on + 1]) > eps)return -1;
}
if (r < on)
return 0;
for (int i = on; i >= 1; i--) {
for (int j = on; j >= i + 1; j--) a[i][on + 1] -= a[i][j] * ans[j];
ans[i] = a[i][on + 1] / a[i][i];
}
return 1;
}
void tarjan(int t){
dfn[t]=low[t]=++dfc;
S.push(t);
for(auto to:G[t]){
if(!dfn[to]){
tarjan(to);
low[t]=min(low[t],low[to]);
}
else if(!be[to])low[t]=min(low[t],dfn[to]);
}
if(low[t]==dfn[t]){
cnt++;
while(S.size()&&S.top()!=t){
be[S.top()]=cnt,scc[cnt].pb(S.top());
S.pop();
}
be[S.top()]=cnt,scc[cnt].pb(S.top());
S.pop();
}
}
bool dfs(int p){
vis[p]=1;
if(be[p]<be[t])return 1;
for(auto to:G[p]){
if(!vis[to]&&dfs(to))return 1;
}
return 0;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
G[u].pb(v),deg[u]++;
}
tarjan(s);
if(!dfn[t]||dfs(s))cout<<"INF",exit(0);
for(int i=1;i<=cnt;i++){
int p=scc[i].size(),cc=0;
memset(a,0,sizeof a);
memset(ans,0,sizeof ans);
for(auto x:scc[i])id[x]=++cc;
for(auto x:scc[i]){
a[id[x]][p+1]=1;
a[id[x]][id[x]]=1;
if(x==t){
a[id[x]][p+1]=0;
continue;
}
if(!deg[x]){
a[id[x]][id[x]]=1,a[id[x]][p+1]=1e6;
continue;
}
for(auto to:G[x]){
if(be[to]!=be[x]){
a[id[x]][p+1]+=f[to]/deg[x];
}
else a[id[x]][id[to]]-=1.0/deg[x];
}
}
Gauss(p);
for(auto x:scc[i])f[x]=ans[id[x]];
}
// for(int i=1;i<=n;i++)cout<<f[i]<<'\n';
if(f[s]<1e10)printf("%.3lf",f[s]);
else cout<<"INF";
return 0;
}