rt，用的dinic，思路和大部分题解一样，实数二分+网络流

前两个点WA我是没想到的……

#include <bits/stdc++.h>
#define ll long long
#define maxn 100005
#define maxm 200005
#define eps 1e-8
#define inf 0x3f3f3f3f
#define mod 998244353
using namespace std;
int n, m;
double P;
struct edge {
	int to, nxt; double w;
} e[maxm << 1];
int p[maxn], eid = 0;
void addedge (int u, int v, double w) {
	e[eid] = (edge){v, p[u], w}, p[u] = eid++;
	e[eid] = (edge){u, p[v], 0}, p[v] = eid++;
}
queue <int> q;
int dep[maxn], ind[maxn], S, T;
bool bfs () {
	while (!q.empty()) q.pop();
	memset (dep, -1, sizeof dep);
	q.push(S), dep[S] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = p[u]; ~i; i = e[i].nxt) {
			int to = e[i].to;
			if (dep[to] == -1 && fabs(e[i].w) > eps) {
				dep[to] = dep[u] + 1;
				if (to == T) return 1;
				q.push(to);
			}
		}
	}
	return 0;
}
double dfs (int u, double lim) {
	if (u == T) return lim;
	double flow = 0;
	for (int &i = ind[u]; ~i; i = e[i].nxt) {
		int to = e[i].to;
		if (dep[to] == dep[u] + 1 && fabs(e[i].w) > eps) {
			double del = dfs (to, min (lim - flow, e[i].w));
			if (fabs(del) < eps) dep[to] = -1;
			flow += del, e[i].w -= del, e[i^1].w += del;
			if (fabs(lim - flow) < eps) break;
		} 
	}
	return flow;
}
double dinic () {
	double flow = 0;
	while (bfs()) {
		for (int i = S; i <= T; i++) ind[i] = p[i];
		flow += dfs (S, 1.0 * inf);
	}
	return flow;
}
int s[maxn], t[maxn]; double c[maxn];
double l = 0, r = 0, mid, ans;
int main () {
	memset (p, -1, sizeof p);
	scanf ("%d %d %lf", &n, &m, &P);
	S = 1, T = n;
	for (int i = 1; i <= m; i++) {
		scanf ("%d %d %lf", s+i, t+i, c+i);
		addedge (s[i], t[i], c[i]);
		r = max (r, c[i]);
	}
	double flow = dinic();
	printf ("%.0f\n", flow);
	while (r - l > eps) {
		mid = (l + r) / 2.0;
		memset (p, -1, sizeof p); eid = 0;
		for (int i = 1; i <= m; i++)
			addedge (s[i], t[i], min(mid, c[i]));
		if (fabs(dinic() - flow) < eps) ans = mid, r = mid;
		else l = mid;
	}
	printf ("%.5f\n", ans * P);
	return 0;
}