Chieh's Blog

Because Of Coding

HDU 5277 YJC counts stars

Chieh posted @ 2015年7月05日 11:43 in BestCoder , 305 阅读

飞机票：http://acm.hdu.edu.cn/showproblem.php?pid=5277

题意：就是给你n个点n个坐标xi,yi(1<=i<=n)，然后给你m条边，表示u和v相连,保证没重边，也保证没有边相交。然后 让你求最大的点子集，使里面的点可以两两相连(不是图相连，线段相连)，且求处个数。

分析:其实分析分析，就发现最大就只有4个点的点急，因为5个点就会有边相交，与题目不符，所以只要枚举到4个点就行了，具体怎么枚举才比较好？可以先枚举两两的，就是加入i和j有边相连，就把i和j算一对保存起来，这样我们就知道两两相连的子集个数有多少个了，怎么枚举三个的，很简单，只要把两个相连的与一个个点比较，只要这两个点能同事与第三个点连接，那么就是ok的，这里注意：假设i和j和k是属于三个相连的，我们求出来两两的就是(i,j)(i,k)(j,k)然后枚举三个点的时候会有三种方法，但是实际上就只有1种，所以答案要/3，这样我们就知道三个点的自己个数了，现在是四个点了，四个点也很方便，只要把两个点的两两进行判断就行了，只要互不相同然后互相连接就可以了，但是要注意:假设我们i，j，p,q，是四个相连的点集，那么我们两两求出来的就是(i,j)(i,p)(i,q)(j,p)(j,q)(p,q)，这样的话，他们两两按数序的话会求出来三组，因为我们重复计算了，所以答案要/3到此为止，所有的都已经判断了， 按照4,3,2,1只要有一个是满足的，直接ok，结束。然后啪啪啪就可以AC了

?
G++ code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234;
int x[maxn],y[maxn];
int ai[maxn][maxn];
int n,m;
void init()
{
    for(int i=1; i<=n; i++)scanf("%d%d",&x[i],&y[i]);
    int u,v;
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        ai[u][v]=ai[v][u]=1;
    }
}
int bi[maxn*maxn][2];
void play()
{
    if(m==0)
    {
        printf("1 %d\n",n);
        return;
    }
    if(m==1)
    {
        printf("2 1\n");
        return ;
    }
    int st=1;
    int sum2=0;
    //判断连通性
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            if(ai[i][j])
            {
                bi[st][0]=i;
                bi[st][1]=j;
                st++;
                sum2++;
            }
        }
    }
    int sum3=0;
    //判断三个点的
    for(int i=1; i<st; i++)
    {
        for(int j=1; j<=n; j++)
        {
            int u=bi[i][0];
            int v=bi[i][1];
            if(ai[u][j]&&ai[v][j])
            {
                sum3++;
            }
        }
    }
    int sum4=0;
    //判断四个点的
    for(int i=1; i<st; i++)
    {
        for(int j=i+1; j<st; j++)
        {
            int u1=bi[i][0];
            int u2=bi[i][1];
            int v1=bi[j][0];
            int v2=bi[j][1];
            if(u1!=v1&&u1!=v2&&u2!=v1&&u2!=v2&&ai[u1][v1]&&ai[u1][v2]&&ai[u2][v1]&&ai[u2][v2])sum4++;
        }
    }
    if(sum4!=0)
    {
        printf("4 %d\n",sum4/3);
 
    }
    else if(sum3!=0)
    {
        printf("3 %d\n",sum3/3);
    }
    else if(sum2!=0)
    {
        printf("2 %d\n",sum2);
    }
 
 
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter