Construct a graph whose vertices are cities and edges are ferry routes. The answer is $n-1$. Let $A, B$ be the set of the cities on the left side and the right side of Hung river, respectively. Let $C, D$ be the set of convenient cities in $A, B$, respectively. Let $N(V)$ denote the union of the neighbors of vertices in $V$. By Hall Theorem: Hung river is clear $\iff\forall S\subseteq A,\ |N(S)|\geq|S|$. Since Hung river is unclear, $\exists S\subseteq A$ s.t. $|N(S)|<|S|$. Clearly, $S\subseteq A-C$. If $S\neq A-C$, there exists $v\in A-C-S$. Since $N(v)\subsetneq B$, after adding an edge from $v$ to $u\in B-N(v)$, $N(S)$ is still the same, and Hung river is still unclear, contradiction. Therefore, $S=A-C$. Since adding an edge will increase $|N(S)|$ by at most $1$, $|N(S)|=|S|-1$. Since after adding an edge, $|N(S)|\geq|S|$, which should increase by at least $1$. We should not be able to add an edge between $S$ and $N(S)$, which means the induced graph from $S\cup N(S)$ is $K_{S, N(S)}$. $\Rightarrow N(S)\subseteq D$ since all vertices in $N(S)$ should be connected to vertices in both $S(=A-C)$ and $C$. On the other hand, $D\subseteq N(S)$ since every vertex in $D$ is connected to every vertex in $A$ including those in $S$. $\therefore$ the number of convenient cities $=|C|+|D|=|C|+|N(S)|=|C|+|S|-1=|C|+|A-C|-1=|A|-1=n-1$.

Kőnig's Theorem

Assume that $k$ is a possible value, let's prove $k\geq n-1$. Proof: Induct on $n$, base case is trivival ($k\geq 0$). If $k<x-1$ won't work for $n=x$, that means adding one edge won't give a perfect matching. When $n=x+1$ we can find a subgraph with $x$ vertices with less than $x-1$ edges, so $k<x$ won't work for $n=x+1$. Now we prove that $k=n-1$ works. The construction is a graph with a $K_{n,n-1}$ subgraph and a vertex with degree $0$. Now we prove that $k\leq n-1$. Proof: Assume $k>n-1$, if all convenient cities are on the same side, then the graph is $K_{n,n}$ which is not okay. Now let the two sides have $\ell,m$ convenient cities each and $\ell+m>n-1$, and color them red and blue respectively. Now pick all red point on a side and all uncolored and some blue points on the other side, they form a $K_{\ell,\ell}$. The rest of the point form a $K_{n-\ell,n-\ell}$. Notice the size of the minimal vertex cover in the two subgraph is $\ell$ and $n-\ell$, respectively. Moreover, they does not intersect. So the original graph has a minimal vertex cover of size $n$, which means there's a perfect matching by Kőnig's.