题解洛谷 P2691【逃离】

最大流。

题目中的起始点肯定是要被超级源连上的。考虑到要求这 \(m\) 个点能通过 \(m\) 条不在格点相交的路径连到边界上，流的方法大致就是沿着网格线，然后边界点连超级汇，权值都是 \(1\)。另外，每个点只能在不超过一条路径上，只是这样会被重复流过，需要搞一遍拆点的套路。

这题的网络流建模挺经典的。

//By: Luogu@rui_er(122461)
#include 
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e4+5, M = 5e5+5, inf = 0x3f3f3f3f; 

int n_, m_, n, m, s, t, dis[N], now[N];
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
struct Edge {
	int v, w, nxt;
	Edge(int a=0, int b=0, int c=0) : v(a), w(b), nxt(c) {}
	~Edge() {} 
}e[M];
int h[N], ne = 1;
void add(int u, int v, int w) {
	e[++ne] = Edge(v, w, h[u]); h[u] = ne;
	e[++ne] = Edge(u, 0, h[v]); h[v] = ne;
}
queue q;
int dfs(int u, int lim) {
	if(u == t || !lim) return lim;
	int res = 0;
	for(int i=now[u];i;now[u]=i=e[i].nxt) {
		int v = e[i].v, w = e[i].w;
		if(dis[v] == dis[u] + 1) {
			int qwq = dfs(v, min(w, lim));
			if(!qwq) continue;
			e[i].w -= qwq; e[i^1].w += qwq;
			lim -= qwq; res += qwq;
			if(!lim) break;
		}
	}
	return res;
}
bool bfs() {
	rep(i, 1, n) {
		dis[i] = inf;
		now[i] = h[i];
	}
	dis[s] = 0;
	q.push(s);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int i=h[u];i;i=e[i].nxt) {
			int v = e[i].v, w = e[i].w;
			if(!w || dis[v] < inf) continue;
			dis[v] = dis[u] + 1;
			q.push(v);
		}
	}
	return dis[t] < inf;
}
int dinic() {
	int flow = 0;
	while(bfs()) flow += dfs(s, inf);
	return flow;
}
int getId(int x, int y) {
	return (x - 1) * n_ + y;
}

int main() {
	scanf("%d%d", &n_, &m_);
	s = 2 * n_ * n_ + 1;
	n = t = s + 1;
	rep(i, 1, m_) {
		int x, y;
		scanf("%d%d", &x, &y);
		add(s, getId(x, y), 1);
	}
	rep(i, 1, n_) {
		rep(j, 1, n_) {
			add(getId(i, j), n_*n_+getId(i, j), 1);
			if(i > 1) add(n_*n_+getId(i, j), getId(i-1, j), 1);
			if(j > 1) add(n_*n_+getId(i, j), getId(i, j-1), 1);
			if(i < n_) add(n_*n_+getId(i, j), getId(i+1, j), 1);
			if(j < n_) add(n_*n_+getId(i, j), getId(i, j+1), 1);
			if(i == 1 || j == 1 || i == n_ || j == n_) add(n_*n_+getId(i, j), t, 1);
		}
	}
	puts(dinic()==m_?"YES":"NO");
    return 0;
}