作业帮ACM模拟题求解Alice lives in the country where people like to make friends. The friendship is bidirectional and if any two person have no less thankfriends in common, they will become friends in several days. Currently, there are totallynpeople i
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/01 13:45:12
ACM模拟题求解Alice lives in the country where people like to make friends. The friendship is bidirectional and if any two person have no less thankfriends in common, they will become friends in several days. Currently, there are totallynpeople i
ACM模拟题求解
Alice lives in the country where people like to make friends. The friendship
is bidirectional and if any two person have no less thankfriends in
common, they will become friends in several days. Currently, there are totallynpeople in the country, andmfriendship among them.
Assume that any new friendship is made only when they have sufficient friends in
common mentioned above, you are to tell how many new friendship are made after a
sufficiently long time.
Input
There are multiple test cases.
The first lien of the input contains an integerT(about 100)
indicating the number of test cases. ThenTcases follow. For each
case, the first line contains three integersn, m, k(1 ≤n≤ 100, 0 ≤m≤n×(n-1)/2, 0 ≤k≤n, there will be no duplicated friendship) followed bymlines showing the current friendship. Theithfriendship contains two
integersui, vi(0 ≤ui,
vi
ACM模拟题求解Alice lives in the country where people like to make friends. The friendship is bidirectional and if any two person have no less thankfriends in common, they will become friends in several days. Currently, there are totallynpeople i
这是哪里的题目,一分都不给,这个排版看的好累,先睡个午觉再说
没想出来好方法
先用暴力吧,把数据处理一下
第一步：数组s[n+1][n+1]
[0]存放朋友的个数,[i]表示是否是第i个人的朋友 "0"表示不是,“1”表示是,“-1”就是自己了
第二步：依然是n+1*n+1的数组
[0]不变,[i]=“-1”表示第i个人已是朋友或者是自己,[i]=other表示与第i个人共同的朋友数
第三步：开始建立友谊, 循环搜
对s[][0]>=k的人,若有[][i]>=k
与i建立友谊,s[][0]++; s[][i]=-1; s[i][]=-1; answer++; s[i][0]++;
哦,失败,还要再处理与他们建立友谊了的人的数据.
总之就是这样,循环至没有满足条件的
数据结构有待优化,因为我只用数组 ：—《
大概的时间
主要是第三步：循环次数（n^2）* 搜索（n) *处理（n*2) = n^4
n=100也可能会超时