Go Running【二分图匹配】

来源

http://acm.hdu.edu.cn/showproblem.php?pid=6808

思路

报告时刻为t，位置为x，那么相同的t+x或者t−x的点能够被一个人（线段）覆盖。
转化为二分图匹配，选择最少的直线，能够包括所有给定的点。
离散化后用dinic求最大流，即为原图的最小点覆盖。
注意maxm要开四倍空间，因为一个点产生两个线段，一个线段需要正反两条边。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define dd(x) cout << #x << "=" << x << ","
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(b-1);i>=a;--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl "
"
#define lowbit(x) x&(-x)
#define inf 0x3f3f3f3f
const int maxn=400010;
const int maxm=400010;

struct edge{
	int to,next,cap,flow;
}edge[maxm];
int tol;
int head[maxn];
void init(){
	tol = 2;
	memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw=0){
	edge[tol].to=v;
	edge[tol].cap=w;
	edge[tol].flow=0;
	edge[tol].next=head[u];
	head[u]=tol++;
	edge[tol].to=u;
	edge[tol].cap=rw;
	edge[tol].flow=0;
	edge[tol].next=head[v];
	head[v]=tol++;
}
int q[maxn];
int dep[maxn],cur[maxn],sta[maxn];
bool bfs(int s,int t,int n){
	int front=0,tail=0;
	memset(dep,-1,sizeof(dep));
	dep[s]=0;
	q[tail++]=s;
	while (front<tail){
		int u=q[front++];
		for (int i=head[u]; i!=-1; i=edge[i].next){
			int v=edge[i].to;
			if (edge[i].cap>edge[i].flow && dep[v]==-1){
				dep[v]=dep[u]+1;
				if (v==t) return true;
				q[tail++] = v;
			}
		}
	}
	return false;
}

int dinic(int s,int t,int n){
	int maxflow=0;
	while (bfs(s,t,n)){
		for (int i=0; i<n; i++) cur[i]=head[i];
		int u=s,tail=0;
		while (cur[s]!=-1){
			if (u==t){
				int tp=inf;
				for (int i=tail-1; i>=0; i--)
					tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
				maxflow+=tp;
				for (int i=tail-1; i>=0; i--){
					edge[sta[i]].flow+=tp;
					edge[sta[i]^1].flow-=tp;
					if (edge[sta[i]].cap-edge[sta[i]].flow==0) 
						tail=i;
				}
				u=edge[sta[tail]^1].to;
			}
			else if (cur[u]!=-1 && edge[cur[u]].cap>edge[cur[u]].flow
			&& dep[u]+1==dep[edge[cur[u]].to]){
				sta[tail++]=cur[u];
				u=edge[cur[u]].to;
			}
			else{
				while (u!=s && cur[u]==-1)
					u=edge[sta[--tail]^1].to;
				cur[u]=edge[cur[u]].next;
			}
		}
	}
	return maxflow;
}

int x[maxn],y[maxn];
vector<int> V1,V2;
#define r1(x) lower_bound(all(V1),x)-V1.begin()
#define r2(x) lower_bound(all(V2),x)-V2.begin()

int main(){
    int T;
    cin>>T;
    while (T--){
    	int n;
    	scanf("%d",&n);
    	V1.clear();
    	V2.clear();
    	for (int i=1; i<=n; i++){
    		scanf("%d%d",&x[i],&y[i]);
    		V1.pb(x[i]+y[i]);
    		V2.pb(x[i]-y[i]);
		}
		sort(all(V1));
		V1.erase(unique(all(V1)),V1.end());
		sort(all(V2));
		V2.erase(unique(all(V2)),V2.end());
		init();
		int s=sz(V1)+sz(V2),t=s+1;
		for (int i=1; i<=n; i++)
			addedge(r1(x[i]+y[i]),sz(V1)+r2(x[i]-y[i]),1);
		for (int i=0; i<sz(V1); i++)
			addedge(s,i,1);
		for (int i=0; i<sz(V2); i++)
			addedge(sz(V1)+i,t,1);
//		for (int i=0; i<tol; i++){
//			cout<<edge[i].cap<<' '<<edge[i].to<<' '<<edge[i].next<<endl;
//		} 
		printf("%d
",dinic(s,t,sz(V1)+sz(V2)+2));
	}
    return 0;
}

参考文献

[1] https://blog.csdn.net/weixin_43828245/article/details/107700724
[2] https://blog.csdn.net/qq_43680965/article/details/107700559
[3] https://blog.csdn.net/weixin_43828245/article/details/107700724
[4] https://www.cnblogs.com/stelayuri/p/13405914.html