题面:
小C来到了F国，小C想好好地参观F国。F国可以看一个有n个点m条边的有向无环图，小C刚开始站在1号点。假设现在小C站在x号点：
1．点x没有出边，结束旅游。
2．点x有o条出边，小C等概率地选一条边走过去。
小J是小C的好朋友，小J可以使用魔法让一些边消失，但是有一些限制(x,y)：第y条边如果被删掉了，那么第x条边也会受到影响，导致第x条边被删掉。
现在小J想知道，如何删边使得小C所经过的边数期望最大。
第一行三个整数，n,m,k(1 <= n <= 50, 0 <= m <= 500, 0 <= k <= 2000)，代表有n个点，m条边，k个限制。
接下来m行，第i行代表第i条边x,y(1 <= x, y <= n)，方向是从x到y。
接下来k行，每行有两个整数x,y(1 <= x, y <= m)，代表限制。
保证图是有向无环的，保证对于每个限制(x,y)，第x条边和第y条边的起点是相同的。可能有重边，限制可能重复。
1 <= n <= 50, 0 <= m <= 500, 0 <= k <= 2000
首先既然是有向无环图,那么如果最优决策中从点x出发的期望步数最多,且从x向y有一条边,必然从y出发的期望步数也达到最多，那么我们按拓扑序依次求出从每个点出发的期望最大步数f[x]即可.
假设我们已经知道了从x出发能到达的所有点的f值,并选择了j条边保留,那么f[x]=1+sigma{f[y],保留的某条边从x指向y}/j,每保留一条边,分子和分母都会增加,相当于保留的边指向的f值的平均值最大，相当于01分数规划,二分这个平均值即可.二分之后每条边有一个权值,如果能选出一些边使得权值和大于0说明答案大于等于当前判断的值.那么接下来跑最大权闭合子图即可.
注意最大权闭合子图的建模是不需要对SCC缩点也能跑的,NOI植物大战僵尸是因为SCC不能选所以需要缩点.我比较简单无脑缩点直接上了于是飙到170行+...不过namespace大法吼啊….被调试续了1h，最后发现我把题读错了,限制的x,y是y删了导致x一定被删不是x删了导致y被删…..新技能get:调代码调不动的时候重新读一遍题有奇效！
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double eps=1e-;
int cmp(double x){return x<-eps?-:x>eps;}
namespace DINIC{
const int maxn=,maxm=;
struct edge{
int to,next;double w;
}lst[maxm];int len=,first[maxn],_first[maxn];
void clear(){
memset(first,-,sizeof(first));len=;
}
void addedge(int a,int b,double w){
lst[len].to=b;lst[len].next=first[a];lst[len].w=w;first[a]=len++;
lst[len].to=a;lst[len].next=first[b];lst[len].w=;first[b]=len++;
}
int q[maxn],vis[maxn],dis[maxn],head,tail,T,s,t;
bool bfs(){
head=tail=;vis[s]=++T;dis[s]=;q[tail++]=s;
while(head!=tail){
int x=q[head++];
for(int pt=first[x];pt!=-;pt=lst[pt].next){
if(lst[pt].w>eps&&vis[lst[pt].to]!=T){
vis[lst[pt].to]=T;q[tail++]=lst[pt].to;dis[lst[pt].to]=dis[x]+;
}
}
}
if(vis[t]==T)memcpy(_first,first,sizeof(first));
return vis[t]==T;
}
double dfs(int x,double lim){
if(x==t)return lim;
double flow=,a;
for(int pt=_first[x];pt!=-;pt=lst[pt].next){
if(lst[pt].w>eps&&dis[lst[pt].to]==dis[x]+&&(a=dfs(lst[pt].to,min(lst[pt].w,lim-flow)))>eps){
lst[pt].w-=a;lst[pt^].w+=a;flow+=a;
if(cmp(flow-lim)==)return flow;
}
}
return flow;
}
double dinic(){
double ans=,x;
while(bfs())while((x=dfs(s,1e5))>eps)ans+=x;
return ans;
}
};
namespace Tarjan{
const int maxm=,maxn=;
struct edge{
int to,next;
}lst[maxm],lst2[maxm];int len=,first[maxn],len2=,first2[maxn];
void addedge(int a,int b){
lst[len].to=b;lst[len].next=first[a];first[a]=len++;
}
void addedge2(int a,int b){
lst2[len2].to=b;lst2[len2].next=first2[a];first2[a]=len2++;
}
int dfn[maxn],low[maxn],s[maxn],top,belong[maxn],tot,T;bool ins[maxn];
void dfs(int x){
dfn[x]=low[x]=++T;ins[x]=true;s[top++]=x;
for(int pt=first[x];pt;pt=lst[pt].next){
if(!dfn[lst[pt].to]){
dfs(lst[pt].to);
if(low[lst[pt].to]<low[x])low[x]=low[lst[pt].to];
}else if(ins[lst[pt].to]&&dfn[lst[pt].to]<low[x])low[x]=dfn[lst[pt].to];
}
if(dfn[x]==low[x]){
++tot;
do{
ins[s[--top]]=false;belong[s[top]]=tot;
}while(s[top]!=x);
}
}
void tarjan(int n,int m){
int x,y;
for(int i=;i<=m;++i){
scanf("%d%d",&x,&y);addedge(x,y);//选x必须选y
}
for(int i=;i<=n;++i){
if(!dfn[i])dfs(i);
}
for(int i=;i<=n;++i){
for(int pt=first[i];pt;pt=lst[pt].next){
if(belong[i]!=belong[lst[pt].to]){
addedge2(belong[i],belong[lst[pt].to]);
}
}
}
}
};
namespace Main{
const int maxm=,maxn=;
int n,m,k;
struct edge{
int to,next,num;
}lst[maxm];int len=,first[maxn];
void addedge(int a,int b,int i){
lst[len].to=b;lst[len].next=first[a];lst[len].num=i;first[a]=len++;
}
int sz[maxm];
bool vis[maxn];
double f[maxn];
double sum[maxm];
int scc[maxm];int tot=;
int sccused[maxm],T;
bool check(double ans){
DINIC::clear();using DINIC::addedge;using DINIC::s;using DINIC::t;
s=;t=m+;
double ori=;
for(int i=;i<=tot;++i){
int x=scc[i];
if(cmp(sum[x]-ans*sz[x])>=){
addedge(s,x,sum[x]-ans*sz[x]);ori+=sum[x]-ans*sz[x];
}
else addedge(x,t,ans*sz[x]-sum[x]);
}
using Tarjan::first2;using Tarjan::lst2;
for(int i=;i<=tot;++i){
for(int pt=first2[scc[i]];pt;pt=lst2[pt].next){
addedge(scc[i],lst2[pt].to,1e5);
}
}
return cmp(ori-DINIC::dinic())>;
}
void getf(int x){
using Tarjan::belong;
if(!first[x])f[x]=;
else{
tot=;++T;
for(int pt=first[x];pt;pt=lst[pt].next){
sum[belong[lst[pt].num]]+=f[lst[pt].to];
sz[belong[lst[pt].num]]++;
if(sccused[belong[lst[pt].num]]!=T){
sccused[belong[lst[pt].num]]=T;scc[++tot]=belong[lst[pt].num];
}
}
double l=,r=;
while(r-l>1e-){
double mid=(l+r)/2.0;
if(check(mid))l=mid;
else r=mid;
}
f[x]=l+;
}
}
void dfs(int x){
vis[x]=true;
for(int pt=first[x];pt;pt=lst[pt].next){
if(!vis[lst[pt].to])dfs(lst[pt].to);
}
getf(x);
}
void work(){
scanf("%d%d%d",&n,&m,&k);
int x,y;
for(int i=;i<=m;++i){
scanf("%d%d",&x,&y);addedge(x,y,i);
}
Tarjan::tarjan(m,k);
for(int i=;i<=n;++i){
if(!vis[i])dfs(i);
}
printf("%.10f\n",f[]);
}
};
int main(){
Main::work();
return ;
}