hdu5277 YJC counts stars（最大团）

题意：

在一张平面图中，给一些点（用坐标表示）和一些边，求最大团，如果最大团有多个统计其数量

解题思路：

本题和普通的最大团问题不同，题目给出了一些限制条件：平面图上给出的任意两条线段除了可以在结点处相连，不能出现交叉现象

画图分析可以发现最大团为4，不可能超过4.

因此我们可以枚举大小为4的团，如果不存在枚举大小为3的团。。。

枚举大小为4的团：我们可以通过枚举两条不同的边，判断两条边没有交点，同时每个点都与另外一条边的点相连；

注意：在枚举过程中会出现重复，我们观察可以发现团大小为4在枚举过程中重复出现了3次，所以最终结果要除以3

枚举大小为3的团：我们可以通过枚举一条边和一个点，判断点不是边的点，同时点和边的每个端点有边相连；

注意：和上面一样，每个重复了3次，最终结果要除3

如果4、3都不存在，则看m是否为0，如果不为0则存在大小为2的团，个数为m

否则只存在大小为1的团，个数为n

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAXN 1010
using namespace std;
struct node{int x,y;node(int _x,int _y):x(_x),y(_y){}
};
vector<node> vc;
int ans[5];
bool flag[MAXN][MAXN];
int n,m;
int main(){while(scanf("%d%d",&n,&m)==2){int tmp;for(int i=1;i<=n;++i)scanf("%d%d",&tmp,&tmp);memset(flag,false,sizeof(flag));int x,y;vc.clear();for(int i=1;i<=m;++i){scanf("%d%d",&x,&y);flag[x][y]=true;flag[y][x]=true;vc.push_back(node(x,y));}memset(ans,0,sizeof(ans));ans[1]=n;ans[2]=m;int len=vc.size();for(int i=0;i<len;i++){for(int j=i+1;j<len;j++){node a=vc[i];node b=vc[j];if(a.x!=b.x&&a.x!=b.y&&a.y!=b.x&&a.y!=b.y){if(flag[a.x][b.x]&&flag[a.x][b.y]&&flag[a.y][b.x]&&flag[a.y][b.y])ans[4]++;}}}if(ans[4]!=0){printf("%d %d\n",4,ans[4]/3);continue;}for(int i=0;i<len;i++){for(int j=1;j<=n;j++){node a=vc[i];if(a.x!=j&&a.y!=j&&flag[a.x][j]&&flag[a.y][j]){ans[3]++;}}}if(ans[3]!=0){printf("%d %d\n",3,ans[3]/3);continue;}if(ans[2]!=0){printf("%d %d\n",2,ans[2]);continue;}if(ans[1]!=0){printf("%d %d\n",1,ans[1]);continue;}}return 0;
}