传送门

网络流的建图真的好难！

将一个点拆分成多个点的思想还需要加强。

题解

代码和题解中的图略不一样。

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#define N 1000001using namespace std;int n, m, cnt, s, t;int head[N], to[N], nex[N], val[N], cost[N], dis[N], pre[N], path[N];bool vis[N];double tim;inline int read()inline void add(int x, int y, int z, int v)inline bool spfa()}}}return pre[t] != 1;}int main()add(s, j + (i  1) * m, 1, 0);add(j + (i  1) * m, s, 0, 0);}for(i = 1; i <= n; i++)while(spfa())}printf("%.2lf\n", double(tim / n));return 0;}