别样的找UB大战
  • 板块学术版
  • 楼主Xdik
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/12/23 22:12
  • 上次更新2024/12/24 17:01:04
查看原帖
别样的找UB大战
700106
Xdik楼主2024/12/23 22:12

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;
}
2024/12/23 22:12
加载中...