二分图匈牙利也可以
判断必须点就看能不能通过偶数长度的增广路翻过去
代码：
（最后一个点4s多才行，，，卡不过算了）
开始边数写少了RE，应该是4*N*N
M-R随手开了一堆int？都要是long long
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define reg register int
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=+;
ll a[N][N];
int co[N*N];
int in[N*N];
int n,m;
struct node{
int nxt,to;
}e[*N*N];
int hd[N*N],cnt;
int num(int x,int y){
return (x-)*m+y;
}
void add(int x,int y){
// cout<<" ahahhaa "<<endl;
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
int to[N*N];
int vis[N*N];
bool dfs(int x,int id){
// cout<<" x "<<x<<" id "<<id<<endl;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
// cout<<" yy "<<y<<" vis "<<vis[y]<<endl;
if(vis[y]==id) continue;
vis[y]=id;
if(!to[y]||dfs(to[y],id)){
to[y]=x;
in[x]=;
to[x]=y;
in[y]=;
return true;
}
}
return false;
}
bool fin(int x,int id,int pos){
if(vis[x]==id) return false;
vis[x]=id;
if(pos==){
if(!to[x]) return true;
return fin(to[x],id,pos^);
}
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y!=to[x]){
if(fin(y,id,pos^)) return true;
}
}
return false;
}
ll p[]={,,,,};
ll add(ll x,ll y,ll p){
return x+y>=p?x+y-p:x+y;
}
ll qk(ll x,ll y,ll p){
ll ret=;
while(y){
if(y&) ret=add(ret,x,p);
x=add(x,x,p);
y>>=;
}
return ret;
}
ll qm(ll x,ll y,ll p){
ll ret=;
while(y){
if(y&) ret=qk(ret,x,p);
x=qk(x,x,p);
y>>=;
}
return ret;
}
bool che(ll x,ll d){
int s=;
ll lp=x-;
while(!(lp&)){
++s;lp>>=;
}
ll now=qm(d,lp,x);
if(now==||now==x-) return true;
for(reg i=;i<s;++i){
ll tmp=qk(now,now,x);
if(tmp==&&(now!=&&now!=x-)) return false;
now=tmp;
}
if(now!=) return false;
return true;
}
bool M_R(ll x){
// cout<<" xx "<<x<<endl;
if(x==) return true;
if(x==) return true;
if(x==46856248255981ll) return false;
if(x==||x==||x==||x==||x==||x==||x==||x==||x==||x==||x==) return true;
for(reg i=;i<;++i){
if(x%p[i]==) return false;
if(!che(x,p[i])) return false;
}
// cout<<" ok "<<endl;
return true;
}
int mem[N*N],nb;
int main(){
// cout<<" M_R "<<M_R(1557403521852231)<<endl;
rd(n);rd(m);
// cout<<" 2333 "<<endl;
for(reg i=;i<=n;++i){
for(reg j=;j<=m;++j){
scanf("%lld",&a[i][j]);
co[num(i,j)]=(i+j)%;
}
} // return 0;
for(reg i=;i<=n;++i){
for(reg j=;j<=m;++j){
if(a[i][j]==-) continue;
if(j!=m){
if(a[i][j+]!=-){
if(M_R(a[i][j]+a[i][j+])==){
add(num(i,j),num(i,j+));
add(num(i,j+),num(i,j));
}
}
}
if(i!=n){
if(a[i+][j]!=-){
if(M_R(a[i][j]+a[i+][j])==){
add(num(i,j),num(i+,j));
add(num(i+,j),num(i,j));
// cout<<num(i,j)<<" "<<num(i+1,j)<<endl;
}
}
}
}
}
// cout<<" after build "<<endl;
int tot=;
int le=,ri=;
for(reg i=;i<=n;++i){
for(reg j=;j<=m;++j){
if(co[num(i,j)]==&&a[i][j]!=-){
++le;
tot+=dfs(num(i,j),num(i,j));
}else if(a[i][j]!=-) ++ri;
}
}
// cout<<" le ri "<<le<<" "<<ri<<" tot "<<tot<<endl;
if(le==ri&&tot==le){
puts("");return ;
}
memset(vis,,sizeof vis);
for(reg i=;i<=n;++i){
for(reg j=;j<=m;++j){
if(a[i][j]!=-){
if(!in[num(i,j)]||fin(to[num(i,j)],num(i,j),)){
mem[++nb]=num(i,j);
}
}
}
}
sort(mem+,mem+nb+);
printf("%d\n",nb);
for(reg i=;i<=nb;++i){
printf("%d %d\n",(mem[i]-)/m+,mem[i]-((mem[i]-)/m)*m);
}
return ;
} }
signed main(){
// freopen("data3618.in","r",stdin);
// freopen("data3618.out","w",stdout);
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/2/2 20:45:23
*/
这个题的二分图匹配思想还是很巧妙
从最大匹配来考虑，便于决策