题意：给定一个平面图求最大团的个数和最大团内的顶点数
数据范围：数据组数T<=5 顶点数<=1000 边数没有给
思路：这是bc的一道题，中文题面语句太随便了，没看明白，看了英文后才看懂原来是一个平面图
定义：一个图G，若可以将它画在平面上,使它的边仅在顶点上才能相交，则称图G为可平面图
在纸上画画便可知最大团的最大为4，，而且每添一个顶点极大平面图的边数只能增加3，而且的确有这个公式：m<=3*n-6
而且答案为4的最大团都是一种形状，枚举两条边，两边无公共点而且两端点互相连通即符合，3n*3n的复杂度可行
然后再处理答案是3，2，1的情况
还有一种思路就是一步到位，枚举点数然后统计4，3，2，1为答案的个数有多少个，可以按点数从小到大遍历，这样不重复，
然后而且复杂度也不是On^4的因为只有m条边，官方题解给了证明是n^2的复杂度，实际跑起来也比较快
3kalili0MS5584K1942BC++2015-07-05 15:15:17
#include <iostream>#include <cstring>#include <cmath>#include <queue>#include <stack>#include <list>#include <map>#include <set>#include <sstream>#include <string>#include <vector>#include <cstdio>#include <ctime>#include <bitset>#include <algorithm>#define SZ(x) ((int)(x).size())#define ALL(v) (v).begin(), (v).end()#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)#define REP(i,n) for ( int i=1; i<=int(n); i++ )using namespace std;typedef long long ll;const int N = 1005;struct Edge{int v,nxt;Edge() {}Edge(int v,int nxt) : v(v),nxt(nxt){}}es[3*N];int cnt;int n,m;int head[N];void inline add_edge(int a,int b){int u = min(a,b),v = max(a,b);es[cnt] = Edge(v,head[u]);head[u] = cnt++;}int mp[N][N];int c[5];void ini(){cnt=0;REP(i,n) REP(j,n) mp[i][j] = 0;REP(i,n) head[i] = -1;REP(i,4) c[i] = 0;}int sta[5];inline bool no(int p,int u){REP(i,p)if(mp[sta[i]][u]==0) return true;return false;}void dfs(int p,int u){c[p]++;if(p == 4) return ;for(int i = head[u];~i;i=es[i].nxt){int v = es[i].v;if(v < u || no(p,v)) continue;sta[p+1] = v;dfs(p+1,v);}}int main(){while(~scanf("%d%d",&n,&m)){ini();REP(i,n){int a,b;scanf("%d%d",&a,&b);}REP(i,m){int u,v;scanf("%d%d",&u,&v);add_edge(u,v);mp[u][v] = mp[v][u] = 1;}REP(i,n){sta[1] = i;dfs(1,i);}if(c[4]) printf("4 %d\n",c[4]);else if(c[3]) printf("3 %d\n",c[3]);else if(c[2]) printf("2 %d\n",c[2]);else if(c[1]) printf("1 %d\n",c[1]);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
当你感到悲哀痛苦时，最好是去学些什么东西。
