C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 524K, 提交时间: 2023-01-03 14:35:03

#include<bits/stdc++.h>
using namespace std;
const int N = 5010, M = 5e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], f[M], w[M], idx, d[N], incf[N], n, m, S, T, pre[N], cnt;
bool st[N];

void add(int a, int b, int c, int d)
{
	e[idx] = b, ne[idx] = h[a], f[idx] = c, w[idx] = d, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = 0, w[idx] = -d, h[b] = idx ++;
}

bool spfa()
{
	queue<int>q;
	memset(d, -0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	d[S] = 0;
	incf[S] = INF;
	q.push(S);

	while(!q.empty())
	{
		auto t = q.front();
		q.pop();
		st[t] = false;
		for(int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if(d[j] < d[t] + w[i] && f[i])
			{
				d[j] = d[t] + w[i];
				pre[j] = i;
				incf[j] = min(incf[t], f[i]);
				if(!st[j])
				{
					st[j] = 1;
					q.push(j);
				}
			}
		}
	}
	return incf[T] > 0;
}	

int EK()
{
	int flow = 0, cost = 0;
	while(spfa())
	{
		flow += incf[T];
		cost += incf[T] * d[T];
		for(int i = T; i != S; i = e[pre[i] ^ 1])
		{
			f[pre[i]] -= incf[T];
			f[pre[i] ^ 1] += incf[T];
		}
	}
	return cost;
}

int a[40][40];

int get(int x, int y)
{
	return (x - 1) * m + y;
}
vector<int>ans[40];

// 1 2 3 4
// 5 6 7 8
void dfs(int u, int id, int fa)
{
	for(int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if(j == fa) continue;
		if(f[i ^ 1] > 0)
		{
			f[i ^ 1] -= 1;
			int a = u, b = j;
			if(b != T)
			{
			if(a > n * m) a -= n * m;
			if(b > n * m) b -= n * m;
			if(b == a + 1) cout << id << " " << 1 << '\n';
			if(b == a + m) cout << id << " " << 0 << '\n';
			}
			dfs(j, id, u);
			break;
		}
	}
}
int main()
{
	memset(h, -1, sizeof h);
	cin >> cnt;
	cin >> m >> n;
	S = 0, T = n * m * 2 + 1;

	add(S, get(1, 1), cnt, 0);
	add(get(n, m) + n * m, T, INF, 0);
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= m; j ++ )
		{
			cin >> a[i][j];
			if(a[i][j] == 1) continue;

			if(a[i][j] == 2)
			{
				add(get(i, j), get(i, j) + n * m, 1, 1);
				add(get(i, j), get(i, j) + n * m, INF, 0);
			}
			else if(a[i][j] == 0)
			{
				add(get(i, j), get(i, j) + n * m, INF, 0);
			}
			if(i != n)
			{
				if(a[i + 1][j] != 1)
					add(get(i, j) + n * m, get(i + 1, j), INF, 0);
			}
			if(j != m)
			{
				if(a[i][j + 1] != 1)
					add(get(i, j) + n * m, get(i, j + 1), INF, 0);
			}	
		}
	EK();
	for(int i = 1; i <= cnt; i ++ )
		dfs(get(1, 1), i, S);
}

C++(clang++11) 解法, 执行用时: 5ms, 内存消耗: 1400K, 提交时间: 2021-01-18 16:30:11

#include<bits/stdc++.h>
using namespace std;
int k,n,m,S,T;
int get(int x,int y){
	return (x*m+y-1)*2;
}
const int N=100000,M=1000000,inf=101010;
struct oppo{
	int to,nex,s,w;
}rod[M];
int head[N],tot;
void add(int from,int to,int s,int w)
{
	rod[tot].nex=head[from];
	rod[tot].to=to;
	rod[tot].s=s;
	rod[tot].w=w;
	head[from]=tot++;
}
void link(int from,int to,int s,int w)
{
	add(from,to,s,w);
	add(to,from,0,-w);
}
int d[N],cur[N];
bool f[N];
bool spfa()
{
	queue<int> v;
	memset(f,0,sizeof(f)); 
	memset(d,-1,sizeof(d));
	d[S]=0,cur[S]=head[S];
	v.push(S);
	while(v.size()){
		int lxl=v.front();v.pop();
		f[lxl]=0;
		for(int i=head[lxl];~i;i=rod[i].nex){
			int to=rod[i].to;
			if(d[to]<d[lxl]+rod[i].w&&rod[i].s){
				d[to]=d[lxl]+rod[i].w;
				cur[to]=head[to];
				if(to==T) return 1;
				if(!f[to]){
					v.push(to);
					f[to]=1;
				}
			}
		}
	}
	return 0;
}
bool vis[N];
int ANS;
int find(int x,int low)
{
	if(x==T){
		ANS+=d[T]*low;
		return low;
	} 
	vis[x]=1;
	int all=0;
	for(int i=cur[x];~i;i=rod[i].nex)
	{
		cur[x]=i;
		int to=rod[i].to;
		if(!vis[to]&&d[to]==d[x]+rod[i].w&&rod[i].s){
			int t=find(to,min(rod[i].s,low-all));
			if(!t) d[to]=-1;
			rod[i].s-=t;
			rod[i^1].s+=t;
			all+=t;
		}
	}
	vis[x]=0;
	return all;
}
void dinic()
{
	while(spfa()) while(find(S,inf));
}
void dfs(int x,int k)
{
	if(x==T) return;
	for(int i=head[x];~i;i=rod[i].nex){
		int to=rod[i].to;
		if(to>x&&rod[i^1].s){
			if(x&1&&to!=T){
				if(to==x+1) printf("%d 1\n",k);
				else printf("%d 0\n",k);
			}
			dfs(rod[i].to,k);
			rod[i^1].s--;
			return;
		}
	}
}
int main()
{
	memset(head,-1,sizeof(head));
	cin>>k>>m>>n;
	S=0,T=get(n,m)+2;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			int t;
			scanf("%d",&t);
			if(t!=1) link(get(i,j),get(i,j)^1,inf,0);
			if(t==2) link(get(i,j),get(i,j)^1,1,1);
		}
	getchar();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(j!=m) link(get(i,j)^1,get(i,j+1),inf,0);
			if(i!=n) link(get(i,j)^1,get(i+1,j),inf,0);
		}
	link(S,get(1,1),k,0);
	link(get(n,m)^1,T,inf,0);
	dinic();
	for(int i=1;i<=k;i++)
		dfs(S,i);
	return 0;
}