2022/2/8

2022/2/8

P3355 骑士共存问题

手画几个点后，发现坐标和奇偶性相同的不会相互攻击

把坐标和按奇偶性划分成两部分，那么这道题就变成了在两部分中放置骑士，使得他们之间没有边相连（即不会相互攻击）

划分成的两部分可以看成二分图，边代表A可以攻击到B。

那么这道题就转换成了求二分图的最大独立集

二分图的最大独立集=顶点数-最大匹配数

用dinic求二分图最大匹配，比匈牙利快。

建模方法： 设坐标和奇偶性为 A ，B两个集合

1. 源点s向A中连一条流量为1的边
2. A朝8个攻击坐标可行处连一条流量为1的边
3. B向汇点t连一条流量为1的边

参考代码

#include
#define ll  long long
#define pii pair
#define si size()
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}


const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int qs=1e6+7;
int a[207][207],n,m;
int s,t,dis[qs],head[qs],nxt[qs],to[qs],p;
int mv[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};

void add(int fx,int tx,ll dx){
	to[p]=tx; dis[p]=dx; nxt[p]=head[fx]; head[fx]=p++;
    //反向边 
  //  cout<<"fx="<n||y<1||y>n||a[x][y]) continue;
					int fy=n*(x-1)+y;
					add(fx,fy,1);
				}
			}
			else add(fx,t,1);
		}
	}
}


//Dinic
ll level[qs],cur[qs];
//level是各点到终点的深度，cur为当前弧优化的增广起点 
bool bfs(){//分层图 
	memset(level,-1,sizeof(level));
	level[s]=0;
	memcpy(cur,head,sizeof(head));
	cur[s]=head[s];
	queue Q;
	Q.push(s);
	while(Q.si){
		int k=Q.front();
		Q.pop();
		for(int i=head[k];i!=-1;i=nxt[i]){
			if(dis[i]>0&&level[to[i]]==-1){
				level[to[i]]=level[k]+1;
				Q.push(to[i]);
				if(to[i]==t) return true;
			}
		}
	}
	return false;
}
ll dfs(int u,ll flow){
	if(u==t) return flow;
	
	ll ret=flow; //剩余的流量
	for(int i=cur[u];i!=-1&&ret>0;i=nxt[i]){
		cur[u]=i;// 当前弧优化
		//如果还能流下去 并且 更深 
		if(dis[i]>0&&level[to[i]]==level[u]+1){
			ll c=dfs(to[i],min(dis[i],ret));
			if(!c) level[to[i]]=-1; //剪枝，出去增广完毕的点 
			ret-=c; //剩余的水流被用了c
			dis[i]-=c;	//减权重 
			dis[i^1]+=c; //反向边加权重 
		}
	} 
	return flow-ret;//返回用掉的水流 
}
//END 

signed main(){
	memset(head,-1,sizeof(head));
	n=read(),m=read();
	int x,y;
	for(int i=1;i<=m;++i){
		x=read(),y=read();
		a[x][y]=1;
	}
	build_map();
	ll ans=n*n-m;
	while(bfs()){
		ans-=dfs(s,inf);
	}
	cout<

#include
#define ll  long long
#define pii pair
#define si size()
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
 
 
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int qs=1e6+7;
 
int n,m,u[qs],f[qs],len[qs],yes[qs];
vector v[qs];
int Find(int x){
	if(x==f[x]) return x;
	return f[x]=Find(f[x]);
}
 
void Merge(int x,int y){
	int fx=Find(x);
	int fy=Find(y);
	if(fx==fy) return;
	f[fx]=fy;
	len[fy]+=len[fx];
}
 
int dfs(int x){
	u[x]=-1;
	for(int i=0;i