题解 P4905 【报纸】
给出一种网络流做法
（因为题解看不懂）
首先建模
给出平面上n个点，可以一次覆盖两个相邻的点，求全部覆盖的最小覆盖次数
考虑让需要覆盖的点经过至少1流量，其它点随意
当覆盖时，需要消耗1费用
可以将相邻两个点连双向边，流量无限（为1也可以，流更多只是浪费），费用为1，最后形状是网格状
然后每个点的流量限制？
对点进行黑白染色，黑点和白点分别与起点和终点相连，如果要求覆盖，则流量下限为1，否则下限为0，上限可以随便
然后跑出合法的最小费用就是答案
这样，需要覆盖的点都有流量，每次覆盖会选择网格上的一条边消耗1费用
最终模型是上下界费用流
关于这个怎么做，可以看看这道题的题解
然而这就完了？
如果用SPFA(?!)跑最短路增广，则程序效率极低
输入150，用了60秒才输出答案
但是已经可以大力打表+耐心等待AC了
据说可以用zkw费用流优化，但是我不会
于是我又瞎改了一下增广的方式
用类似Dinic的方法，每次增广多条最短路线
为了防止无限递归，又瞎弄了一个限制条件：当接下来的点已被访问且边权<=0时，直接跳过
结果就这样过了
又试了试n=1000，本机3秒输出答案
最后是诡异的代码：
#include<iostream>
#define next noCE
using namespace std;
const int N=65536;
int head[N],next[N*10],ver[N*10],edge[N*10],ret[N*10],tot=1;
void add(int a,int b,int e,int f){
tot++;
ret[tot]=f;
edge[tot]=e;
ver[tot]=b;
next[tot]=head[a];
head[a]=tot;
tot++;
ret[tot]=0;
edge[tot]=-e;
ver[tot]=a;
next[tot]=head[b];
head[b]=tot;
}
int que[N*6],he,ta;
bool inque[N];
int dis[N];
int n;
int fr[N];
bool spfa(){
for(int i=1;i<=n*n+4;i++)dis[i]=0x3fffffff;
dis[n*n+3]=0;
he=ta=0;
que[he++]=n*n+3;
inque[n*n+3]=1;
fr[n*n+3]=0;
int cur;
while(he!=ta){
cur=que[ta++];
inque[cur]=0;
for(int i=head[cur];i;i=next[i]){
if(ret[i]==0)continue;
if(dis[ver[i]]>dis[cur]+edge[i]){
dis[ver[i]]=dis[cur]+edge[i];
fr[ver[i]]=i;
if(!inque[ver[i]]){
inque[ver[i]]=1;
que[he++]=ver[i];
}
}
}
}
return dis[n*n+4]<0x3fffffff;
}
int cost;
bool vis[N];
int dfs(int id,int maxf){
if(id==n*n+4)return maxf;
int f=0,ans=0;
vis[id]=1;
for(int i=head[id];i;i=next[i]){
if(ret[i]==0)continue;
if(dis[ver[i]]!=dis[id]+edge[i])continue;
if(edge[i]<=0 && vis[ver[i]])continue;
f=dfs(ver[i],min(ret[i],maxf-ans));
cost+=edge[i]*f;
ret[i]-=f;
ret[i^1]+=f;
ans+=f;
if(ans>=maxf)break;
}
return ans;
}
int mcmf(){
while(spfa()){
for(int i=1;i<=n*n+4;i++)vis[i]=0;
dfs(n*n+1,0x3fffffff);
}
return cost;
}
int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}
int fs,ft;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(gcd(i,j)!=1){
if((i+j)&1){
add(n*n+1,i+n*(j-1),0,1);
fs++;
add(n*n+3,i+n*(j-1),0,1);
}else{
add(i+n*(j-1),n*n+2,0,1);
ft++;
add(i+n*(j-1),n*n+4,0,1);
}
}else{
if((i+j)&1){
add(n*n+1,i+n*(j-1),0,1);
}else{
add(i+n*(j-1),n*n+2,0,1);
}
}
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<=n;j++){
add(i+n*(j-1),i+n*(j-1)-1,1,1);
add(i+n*(j-1)-1,i+n*(j-1),1,1);
}
}
for(int i=1;i<=n;i++){
for(int j=2;j<=n;j++){
add(i+n*(j-1),i+n*(j-1)-n,1,1);
add(i+n*(j-1)-n,i+n*(j-1),1,1);
}
}
add(n*n+1,n*n+4,0,fs);
add(n*n+3,n*n+2,0,ft);
add(n*n+2,n*n+1,0,0x3fffffff);
cout<<mcmf()<<endl;
}最终用时342ms