2020杭電多校4 1007 Go Running(最大流)

タイトル:
一部の学生はx x x軸上を走り、速度は1 1 1であり、2つの方向があり、開始時間、終了時間、開始位置を有することができる.現在n n n個のモニタがあり、各モニタは(t,x)(t,x)(t,x)(t,x)を記録し、t時刻にx x x位置に人がいることを示す.少なくとも何人の学生がランニングに行ったかを聞く.
考え方:
y y y軸を時間とすると、各学生はy=x+b、y=x+b、y=x+b、y=−x+b y=−x+b y=−x+b y=−x+b直線上のセグメントであり、モニタは座標系上の点であり、最小のセグメントをどのように選択して点をすべて覆うかを問う.一方、1つの点については、2つの線に対応して上書きすることができ、1つの点は、1つの二分図マッチング問題に相当し、次に最大マッチングを求め、さらに最大ストリームに変換して解決することができる.
コード:

#include 
#define ll long long
#define inf 0x3f3f3f3f
#define PII pair
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define pb push_back
#define cwk freopen("D:\\c++\\in.txt","r",stdin),freopen("D:\\c++\\out.txt","w",stdout)
using namespace std;
const int N=5e5+10;
const int M=1e6+10;
int T;
int n;
int a[N],b[N];
vector<int>v;
int getid(int x) {
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
struct Maxflow{
	int h[N],cur[N],ne[M],to[M],tot,deep[N],s,t,mx;
	ll flow[M],ans;
	inline void init(int a,int b,int c){
		s=a;t=b;mx=c;
		for(int i=0;i<M;i++)ne[i]=0;
		for(int i=0;i<N;i++)h[i]=0;
		tot=1;ans=0;
	}
	inline void addedge(int x,int y,int z){
		to[++tot]=y;ne[tot]=h[x],h[x]=tot,flow[tot]=z;
		swap(x,y);
		to[++tot]=y;ne[tot]=h[x],h[x]=tot,flow[tot]=0;
	}
	inline bool bfs(){
		for(int i=0;i<=mx;i++)deep[i]=-1;
		queue<int>q;
		q.push(s);deep[s]=0;
		for(int i=0;i<=mx;i++)cur[i]=h[i];
		while(!q.empty())
		{
			int now=q.front();q.pop();
			for(int i=h[now];i;i=ne[i]){
				int v=to[i];
				if(deep[v]==-1&&flow[i]>0)deep[v]=deep[now]+1,q.push(v);
			}
		}
		return deep[t]!=-1;
	}
	inline ll dfs(int u,ll op){
		if(u==t||op==0)return op;
		ll f=0,us=0;
		for(int i=cur[u];i;i=ne[i]){
			cur[u]=i;
			int v=to[i];
			if(deep[v]==deep[u]+1&&flow[i]>0){
				us=dfs(v,min(op,flow[i]));
				if(!us)continue;
				f+=us;op-=us;
				flow[i]-=us;flow[i^1]+=us;
				if(!op)break;
			}
		}
		if(!f)deep[u]=-1;
		return f;
	}
	inline ll maxflow(){
		while(bfs()){
			ans+=dfs(s,inf);
		}
		return ans;
	}
}F;
int main()
{
	//cwk;
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n);
		v.clear();
		for(int i=1;i<=n;i++) 
			scanf("%d%d",&a[i],&b[i]),v.pb(a[i]+b[i]),v.pb(a[i]-b[i]);
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());//   
		int m=v.size();
		F.init(0,2*m+1,2*m+1);
		for(int i=1;i<=m;i++) {
			F.addedge(0,i,1);
			F.addedge(i+m,2*m+1,1);
		}
		for(int i=1;i<=n;i++) {
			int l=getid(a[i]-b[i]);
			int r=getid(a[i]+b[i]);
			F.addedge(l,r+m,inf);
		}
		ll ans=F.maxflow();
		printf("%lld
",ans);
	}

	return 0;
}