hdu 5277 YJC counts stars



题意：

给出一个平面图，n个点，m条边，直线边与直线边之间不相交，求最大团的数目。



限制：

1 <= n <= 1000



思路：

因为平面图，直线边与直线边之间不相交，所以最大团的大小最大为4，m<=3*n-6。

所以对于答案4，枚举两条边。

对于答案3，枚举一条边一个点。

/*hdu 5277

  题意：

  给出一个平面图，n个点，m条边。直线边与直线边之间不相交，求最大团的数目。

限制：

  1 <= n <= 1000

  思路：

  因为平面图。直线边与直线边之间不相交，所以最大团的大小最大为4，m<=3*n-6。

  所以对于答案4，枚举两条边；

  对于答案3，枚举一条边一个点；

 */

#include<iostream>

#include<cstdio>

#include<set>

#include<cstring>

#include<algorithm>

using namespace std;

#define MP make_pair

const int N=5000;

int fr[N],to[N];

int _set[N/4][N/4];

bool in(int f,int t){

	if(f==t) return false;

	if(f>t) swap(f,t);

	return _set[f][t]!=0;

}

bool ok(int i,int j){

	if(in(fr[i],fr[j]) && in(fr[i],to[j]) && in(to[i],fr[j]) && in(to[i],to[j])) return true;

	return false;

}

bool vis[9000010];

int get_id1(int i,int j){

	int a[4];

	a[0]=fr[i];

	a[1]=to[i];

	a[2]=fr[j];

	a[3]=to[j];

	sort(a,a+4);

	return _set[a[0]][a[1]]*3000+_set[a[2]][a[3]];

}

int four(int m){

	memset(vis,0,sizeof(vis));

	int cnt=0;

	for(int i=0;i<m;++i){

		for(int j=i+1;j<m;++j){

			if(ok(i,j)){

				int id=get_id1(i,j);

				if(vis[id]) continue;

				++cnt;

				vis[id]=1;

			}

		}

	}

	return cnt;

}

int get_id(int a,int b,int c){

	if(a>b) swap(a,b);

	if(b>c) swap(b,c);

	int ret=_set[a][b];

	ret=ret*1000+c;

	return ret;

}

int three(int n,int m){

	memset(vis,0,sizeof(vis));

	int cnt=0;

	for(int i=1;i<=n;++i){

		for(int j=0;j<m;++j){

			if(fr[j]==i || to[j]==i) continue;

			//cout<<fr[j]<<' '<<i<<endl;

			//cout<<to[j]<<' '<<i<<endl;

			if(in(i,fr[j]) && in(i,to[j])){

				int id=get_id(i,fr[j],to[j]);

				//cout<<id<<endl;

				if(vis[id]) continue;

				++cnt;

				vis[id]=1;

			}

		}

	}

	return cnt;

}

void gao(int n,int m){

	int ans=4;

	int cnt;

	cnt=four(m);

	if(cnt){ printf("%d %d\n",ans,cnt); return ;}

	--ans;

	cnt=three(n,m);

	//cout<<cnt<<endl;

	if(cnt){ printf("%d %d\n",ans,cnt); return ;}

	--ans;

	cnt=m;

	//cout<<cnt<<endl;

	if(cnt){ printf("%d %d\n",ans,cnt); return ;}

	printf("%d %d\n",1,n);

}

int main(){

	int n,m;

	int x,y;

	while(scanf("%d%d",&n,&m)!=EOF){

		memset(_set,0,sizeof(_set));

		for(int i=0;i<n;++i){

			scanf("%d%d",&x,&y);

		}

		for(int i=0;i<m;++i){

			scanf("%d%d",&fr[i],&to[i]);

			if(fr[i]>to[i]) swap(fr[i],to[i]);

			_set[fr[i]][to[i]]=i+1;

		}

		gao(n,m);

	}

	return 0;

}