潜行世界
- 总时间限制:
- 10000ms
- 内存限制:
- 256000kB
- 描述
HJA和学弟还在旅游中，这次他们来到了潜行世界。潜行世界是一个N个点M条边的有向无环图。每条路对于HJA和学弟都一个吸引指数，我们把它叫做这条边的权值。权值越大，HJA和学弟就越有可能走这条路。假设HJA和学弟现在在点u，点u出发的所有边的权值之和为s，从u到v的边的权值为w，那么他们选择走向v的概率就是。为了使得问题变得更加简单，HJA决定在开始前删掉任意一条边（也可以不删）。当HJA和学弟走到一个没有出边的点时，这次旅行就结束了。HJA想知道，如果他和学弟从零号点出发，他们期望走的长度最长是多少呢？（每条边的长度都为1）
- 输入
- 第一行两个正整数N、M，代表图的点数和边数。
接下来M行每行三个整数S、E、D，代表S到E有一条权值为D的边。 - 输出
- 一行一个实数代表答案，误差不得超过1e-6。（没有spj，有问题就找zhx）
- 样例输入
4 5
0 1 2
0 2 1
0 3 3
1 3 1
2 3 4- 样例输出
2.000000
- 提示
- 对于50%的数据，1≤N≤500。
对于100%的数据，1≤N≤10,000，1≤M≤100,000，所有边权不超过103。 - 来源
- zhonghaoxi
- 這道題在考場上將無向圖與樹搞混了，用樹形DP的思路來做得這道題，上述思路會出現算重的問題。
- 這道題的正解是預處理計算到每個點的概率，在枚舉刪邊。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define MAXN 110000
#define MAXV MAXN*2
#define MAXE MAXV*2
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define PROB "secretbase"
typedef long long qword;
inline int nextInt()
{
char ch;
int x=;
bool flag=false;
do
ch=getchar(),flag=(ch=='-')?true:flag;
while(ch<''||ch>'');
do x=x*+ch-'';
while (ch=getchar(),ch<='' && ch>='');
return x*(flag?-:);
} int n,m;
struct Edge
{
int np,val;
Edge *next;
}E[MAXN],*V[MAXV];
int tope=-;
void addedge(int x,int y,int z)
{
E[++tope].np=y;
E[tope].val=z;
E[tope].next=V[x];
V[x]=&E[tope];
}
int totw[MAXN];
int el[MAXE][];
bool vis[MAXN];
queue<int> Q;
int seq[MAXN],tops=-;
int dego[MAXN];
int degi[MAXN];
double poss[MAXN],g[MAXN];;
int main()
{
freopen(PROB".in","r",stdin);
freopen(PROB".out","w",stdout);
int i,j,k;
int x,y,z;
scanf("%d%d",&n,&m);
for (i=;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
totw[x]+=z;
addedge(x,y,z);
dego[x]++;
degi[y]++;
el[i][]=x;
el[i][]=y;
el[i][]=z;
}
memset(vis,,sizeof(vis));
for (i=;i<n;i++)
{
if (!degi[i])
{
Q.push(i);
vis[i]=true;
}
}
int now;
Edge *ne;
while (!Q.empty())
{
now=Q.front();
Q.pop();
seq[++tops]=now;
for (ne=V[now];ne;ne=ne->next)
{
if (vis[ne->np])continue;
degi[ne->np]--;
if (!degi[ne->np])
{
Q.push(ne->np);
vis[ne->np]=true;
}
}
}
poss[]=;
for (i=;i<=tops;i++)
{
now=seq[i];
for (ne=V[now];ne;ne=ne->next)
{
poss[ne->np]+=poss[now]*ne->val/totw[now];
}
}
tope=-;
memset(V,,sizeof(V));
memset(vis,,sizeof(vis));
for (i=;i<n;i++)g[i]=1e100;
for (i=;i<m;i++)
{
addedge(el[i][],el[i][],el[i][]);
}
for (i=;i<n;i++)
{
if (!dego[i])
{
vis[i]=true;
Q.push(i);
g[i]=;
}
}
tops=-;
while (!Q.empty())
{
now=Q.front();
Q.pop();
seq[++tops]=now;
for (ne=V[now];ne;ne=ne->next)
{
if (vis[ne->np])continue;
dego[ne->np]--;
if (!dego[ne->np])
{
Q.push(ne->np);
vis[ne->np]=true;
}
}
}
// for (i=0;i<=tops;i++)printf("%d ",seq[i]);printf("\n");
memset(V,,sizeof(V));
tope=-;
for (i=;i<m;i++)
{
addedge(el[i][],el[i][],el[i][]);
}
for (i=;i<=tops;i++)
{
now=seq[i];
if (!g[now])continue;
g[now]=;
for (ne=V[now];ne;ne=ne->next)
{
g[now]+=g[ne->np]*ne->val/totw[now];
}
g[now]+=;
}
// for (i=0;i<n;i++)printf("%lf ",g[i]);
double delta=-1e100;
double t;
double gn;
for (i=;i<m;i++)
{
if (totw[el[i][]]==el[i][])
{
gn=;
}else
gn=(g[el[i][]]-(g[el[i][]]+)*el[i][]/totw[el[i][]])*totw[el[i][]]/(totw[el[i][]]-el[i][]);
delta=max((gn-g[el[i][]])*poss[el[i][]],delta);
}
delta=max(0.0,delta);
printf("%.6lf ",g[]+delta);
return ;
}