[TCO2009]NumberGraph

题意：给你一些带权的节点和一个正整数集合$S$，$S$中每一个数的二进制后缀$0$个数相同，节点$x$的权值为$v_x$，如果对于$x,y$存在$t\in S$使得$|v_x-v_y|=t$，那么连边$(x,y)$，现在要找出一个最大的子图使得子图中的节点两两最短距离$\leq2$

第一次用TC客户端上的Arena，特别开心==

如果$S$中每个数末尾有$k$个$0$，那么一条边的两个端点的权值的第$k+1$位必定不同，所以这个图是二分图

接下来相当于是要在二分图的两部分中分别找一个非空点集，使得两个集合中的点两两有边相连，对两部间的边取补后问题变为两两无边相连

因为要求非空所以不能直接跑最大独立集，考虑枚举一对不相邻的，分属二分图两部的节点，硬点他们必须被选，删掉它们和与之相连的边，对剩下的点跑最大独立集即可

#include<vector>
#include<string>
#include<sstream>
#include<algorithm>
#include<string.h>
using namespace std;
const int inf=2147483647;
int lowbit(int x){return x&-x;}
int abs(int x){return x>0?x:-x;}
string str;
int h[90],nex[5010],to[5010],cap[5010],M,S,T;
void ins(int a,int b,int c){
	M++;
	to[M]=b;
	cap[M]=c;
	nex[M]=h[a];
	h[a]=M;
}
void add(int a,int b,int c){
	ins(a,b,c);
	ins(b,a,0);
}
int dis[90],q[90];
bool bfs(){
	int head,tail,x,i;
	memset(dis,-1,sizeof(dis));
	head=tail=1;
	q[1]=S;
	dis[S]=0;
	while(head<=tail){
		x=q[head++];
		for(i=h[x];i;i=nex[i]){
			if(cap[i]&&dis[to[i]]==-1){
				dis[to[i]]=dis[x]+1;
				if(to[i]==T)return 1;
				q[++tail]=to[i];
			}
		}
	}
	return 0;
}
int cur[90];
int dfs(int x,int flow){
	if(x==T)return flow;
	int us=0,i,t;
	for(i=cur[x];i&&flow;i=nex[i]){
		if(cap[i]&&dis[to[i]]==dis[x]+1){
			t=dfs(to[i],min(flow,cap[i]));
			cap[i]-=t;
			cap[i^1]+=t;
			us+=t;
			flow-=t;
			if(cap[i])cur[x]=i;
		}
	}
	if(us==0)dis[x]=-1;
	return us;
}
int dicnic(){
	int ans=0;
	while(bfs()){
		memcpy(cur,h,sizeof(h));
		ans+=dfs(S,inf);
	}
	return ans;
}
bool g[90][90];
int v1[90],v2[90],d[90],n1,n2,lw,cnt;
int gao(int x,int y){
	int i,j,sum;
	cnt++;
	d[x]=cnt;
	for(i=1;i<=n2;i++){
		if(g[x][i])d[i+n1]=cnt;
	}
	d[y+n1]=cnt;
	for(i=1;i<=n1;i++){
		if(g[i][y])d[i]=cnt;
	}
	memset(h,0,sizeof(h));
	M=1;
	sum=0;
	for(i=1;i<=n1;i++){
		if(d[i]!=cnt){
			add(S,i,1);
			sum++;
		}
	}
	for(i=n1+1;i<=n1+n2;i++){
		if(d[i]!=cnt){
			add(i,T,1);
			sum++;
		}
	}
	for(i=1;i<=n1;i++){
		if(d[i]!=cnt){
			for(j=n1+1;j<=n1+n2;j++){
				if(g[i][j-n1]&&d[j]!=cnt){
					add(i,j,1);
				}
			}
		}
	}
	return sum-dicnic()+2;
}
class NumberGraph{
	public:
		int largestSet(vector<string>gs,vector<int>js){
			int x,i,j,k,ans;
			bool flag;
			str="";
			for(i=0;i<(int)gs.size();i++)str+=gs[i];
			istringstream cin(str);
			lw=lowbit(js[0]);
			n1=n2=0;
			while(cin>>x)(x&lw?v1[++n1]:v2[++n2])=x;
			S=n1+n2+1;
			T=S+1;
			for(i=1;i<=n1;i++){
				for(j=1;j<=n2;j++){
					flag=1;
					for(k=0;k<(int)js.size();k++){
						if(abs(v1[i]-v2[j])==js[k]){
							flag=0;
							break;
						}
					}
					g[i][j]=flag;
				}
			}
			ans=1;
			for(i=1;i<=n1;i++){
				for(j=1;j<=n2;j++){
					if(!g[i][j])ans=max(ans,gao(i,j));
				}
			}
			return ans;
		}
};
/*
int main(){
	NumberGraph g;
	vector<string>vs;
	vector<int>vi;
	string s;
	int x;
	ostringstream os;
	scanf("%d",&x);
	while(x){
		os<<x<<' ';
		scanf("%d",&x);
	}
	vs.push_back(os.str());
	scanf("%d",&x);
	while(x){
		vi.push_back(x);
		scanf("%d",&x);
	}
	printf("%d",g.largestSet(vs,vi));
}
*/

巴特西

[TCO2009]NumberGraph

最新文章

热门文章