分析

\(t\) 时刻还有城镇没有被淹没，\(t+1\) 时刻所有城镇将要被淹没。

一个思路是求出最后一个城镇被淹没的时刻 \(D\)，然后通过魔法调整使得所有城镇至少会在 \(D\) 时刻被淹没。显然 \(D\) 就是 \(1\) 到每一个点所有的路径中的最大边权取最小值，猜都能猜到是最小生成树中的最大边权，证明略。

求出 \(D\) 后，我们的目标是使得 \(1 \rightarrow n\) 所有路径中最大边权最小为 \(D\)，否则如果比 \(D\) 小则不满足条件，比 \(D\) 大则显然不优。

对于一条权值为 \(w\) 的边，代价为 \(D - w\)，其中 \(w < D\)。考虑把 \((x,y,D-w)\) 加入图中，那么问题就变成了选择权值和最小的边，使得 \(1\) 和 \(n\) 不连通。原因是如果 \(1\) 和 \(n\) 不连通，那么 \(1 \rightarrow n\) 的所有路径中不存在 \(w < D\) 的边，这就达到了目的。

以 \(1\) 为源点，\(n\) 为汇点，求出图中的最小割即可。

注意这是一张无向图，加边的时候有一些细节。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=30005, M=2e4+5, inf=1e15;
int n, m, D, fa[N], d[N];
int tot=1, h[N], hh[N], to[N<<1], nxt[N<<1], w[N<<1];
struct edge { int u, v, w; } e[M];
bool operator<(edge a,edge b) { return a.w<b.w; }
int get(int x) { return x==fa[x]? x:fa[x]=get(fa[x]); } 
void add(int x,int y,int z) {
	to[++tot]=y, w[tot]=z, nxt[tot]=h[x], h[x]=tot;
}
void addedge(int x,int y,int z) {
	add(x,y,z), add(y,x,z);
}
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void kruskal() {
	for(int i=1;i<=n;++i) fa[i]=i;
	int cnt=0;
	sort(e+1,e+m+1);
	for(int i=1;i<=m;++i) {
		int x=get(e[i].u), y=get(e[i].v);
		if(x!=y) {
			fa[x]=y;
			D=max(D,e[i].w);
			if(++cnt==n-1) break;
		}
	}
}
bool bfs() {
	queue<int> q;
	memset(d,0,sizeof(d));
	d[1]=1, q.push(1);
	while(q.size()) {
		int x=q.front(); q.pop();
		hh[x]=h[x];
		for(int i=h[x];i;i=nxt[i]) {
			int y=to[i], z=w[i];
			if(d[y]||!z) continue;
			d[y]=d[x]+1;
			q.push(y);
			if(y==n) return 1; 
		}
	}
	return 0;
}
int dfs(int x,int flow) {
	if(x==n||!flow) return flow;
	int res=flow;
	for(int& i=hh[x];i;i=nxt[i]) {
		int y=to[i], z=w[i];
		if(d[y]!=d[x]+1||!z) continue;
		int k=dfs(y,min(res,z));
		if(!k) d[y]=0; else w[i]-=k, w[i^1]+=k, res-=k;
		if(!res) return flow;
	}
	return flow-res;
}
int dinic() {
	int ans=0;
	while(bfs()) ans+=dfs(1,inf);
	return ans;
}
signed main() {
	n=read(), m=read();
	for(int i=1;i<=m;++i) {
		e[i].u=read(), e[i].v=read(), e[i].w=read();
	} 
	kruskal();
	for(int i=1;i<=m;++i) {
		int u=e[i].u, v=e[i].v;
		if(D>e[i].w) addedge(u,v,D-e[i].w);
	}
	printf("%lld\n",dinic());
}