absi2011's Blog & Daily Life.

全新的开始　　　　　　　我要省选翻盘　　　　　　　I wanna AK in 高考\化学　　　　　　　自此,生无可恋
[破碎的状态] [-52] Hdu 5471 Count the Grid
[破碎的状态] [-38] 100818 B

[破碎的状态] [-51] UVaLive 6778 - Sensor Network

absi2011 posted @ 9 年前 in 刷题记录 with tags 小高考 瞎搞 图论 , 777 阅读

感谢@JCarlson 翻译

题意:二维平面上有若干个点，选择其中一部分点，要求两两之间距离不超过d。

n<=100

很果断建个图,求最大团

用省选随机法很快就过掉了..

一遍过..

谈谈省选随机法是个什么东西

这玩意儿是我在省选现成的时候瞎搞用的..期望得分10分实际得分100分的东西..不然我就进不了省队了..

后来仔细思考了下,确实是个不错的算法,正确性似乎挺高

1,每次随机找一个点

2,随机找出一个和当前所有选的点都相邻的点

3,把它加入我们的团里面,如果此时还可以继续扩展,再执行2号操作

这样的话,我们随机多次就有很大的正确性

这题我设置的随机边界是5000000,但是其实可能还能再大点

具体的随机边界根据评测机调整即可

代码:

?
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
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
bool a[128][128];
int best_sol[128];
int max_ans=0;
int cnt;
const int TLE=5000000;
int n,d;
void dfs(int x)
{
    static int t[105];
    static int chosen[105];
    int i;
    for (i=0;i<n;i++)
    {
        t[i]=a[x][i];
        chosen[i]=false;
    }
    chosen[x]=true;
    int now_ans=1;
    cnt+=n;
    for (;;)
    {
        static int que[105];
        int prob_sol=0;
        for (i=0;i<n;i++)
        {
            if ((t[i])&&(!chosen[i]))
            {
                que[prob_sol++]=i;
            }
        }
        if (prob_sol+now_ans<=max_ans) return;
        if (prob_sol==0)
        {
            max_ans=now_ans;
            for (i=0;i<n;i++)
            {
                best_sol[i]=chosen[i];
            }
            return;
        }
        cnt+=n;
        int k=que[rand()%prob_sol];
        chosen[k]=true;
        for (i=0;i<n;i++)
        {
            t[i]&=a[k][i];
        }
        now_ans++;
        cnt+=n;
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    for (;scanf("%d%d",&n,&d)!=-1;)
    {
        static int x[105],y[105];
        int i;
        for (i=0;i<n;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
        }
        for (i=0;i<n;i++)
        {
            int j;
            for (j=0;j<n;j++)
            {
                if ((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=d*d) a[i][j]=true; else a[i][j]=false;
            }
        }
        cnt=0;
        max_ans=0;
        for (;;)
        {
            dfs(rand()%n);
            if (cnt>=TLE) break;
        }
        printf("%d\n",max_ans);
        for (i=0;i<n;i++)
        {
            if (best_sol[i]) printf("%d ",i+1);
        }
        printf("\n");
    }
    return 0;
}
Small_feed 评论 (6)
1
[回复]
Avatar_small
SanSiroWaltz 说:
9 年前

这是wf2014的题吧，一个很有趣的二分图匹配

[回复]
Avatar_small
absi2011 说:
9 年前

.......是wf2014的题..然而我再次用省选的办法过了这题....

[回复]
Avatar_small
Recursion 说:
9 年前

这题理论复杂度似乎是O(n^4\sqrt n)的...

[回复]
Avatar_small
absi2011 说:
9 年前

我的复杂度理论是多少的呢....

4
[回复]
Avatar_small
ジミ＝カルソン 说:
9 年前

我啥时候翻译这题的我咋不记得了……

[回复]
Avatar_small
absi2011 说:
9 年前

上个星期..二?


登录 *


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