http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3710
题意：有N个人，M对关系，（a，b）表示a，b互相认识。如果两个不认识的人有不小于K个共同朋友，则这两个人将成为新的朋友。问有多少对能成为新的好朋友。
思路：枚举所有的人，如果两个人不是朋友的话，就通过两个人共同好友个数判断两个人能否成为朋友，如果两个人成为新朋友则需要重新判断没有成为朋友的人，直至没有新的朋友产生。
1 #include <stdio.h> 2 #include <string.h> 3 using namespace std; 4 5 const int N=120; 6 int m[N][N]; 7 int main() 8 { 9 int t; 10 scanf("%d",&t); 11 while(t--) 12 { 13 int N,M,K; 14 scanf("%d%d%d",&N,&M,&K); 15 memset(m,0,sizeof(m)); 16 int u,v; 17 for (int i = 0; i < M; i++) 18 { 19 scanf("%d%d",&u,&v); 20 m[u][v] = 1; //u,v两个人是朋友 21 m[v][u] = 1; 22 } 23 int ans = 0; 24 int flag = 0; 25 while(1) 26 { 27 flag = 0; 28 for (int i = 0; i < N; i++) 29 { 30 for (int j = 0; j < N; j++) 31 { 32 if(i==j) continue; 33 if (m[i][j]==0)//如果两个人不是朋友 34 { 35 int cnt = 0; 36 int k; 37 for (k = 0; k < N; k ++) 38 { 39 if (m[i][k]==1&&m[j][k]==1) 40 cnt++; //统计两个人共同的朋友个数 41 if (cnt >= K) 42 { 43 flag = 1; 44 m[i][j] = 1; 45 m[j][i] = 1; 46 ans++; 47 break; 48 } 49 } 50 } 51 } 52 } 53 if(!flag)//没有新朋友产生 54 break; 55 } 56 printf("%d ",ans); 57 } 58 return 0; 59 }