2013年5月11日zoj比赛残留题 zoj5000 Density of Power Network && zoj5002 Friends

May 11, 2013
zoj

两道水题。直接暴力。数据范围都不大，还没有过，等哪天zoj把题目挂出来了再交。 Density of Power Network 题目链接：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5000


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int edge[502][502], a[502], b[502];
int main(void){
#ifndef ONLINE_JUDGE
  freopen("zoj5000.in", "r", stdin);
#endif
  int t, n, m, i, j, k; scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &m);
    memset(edge, 0, sizeof(edge));
    for (i = 0;i < m; ++i) {scanf("%d", &a[i]); a[i]--;}
    for (i = 0;i < m; ++i) {scanf("%d", &b[i]); b[i]--;}
    for (i = 0;i < m; ++i) edge[a[i]][b[i]] = edge[b[i]][a[i]]= 1;
    k = 0;
    for (i = 0; i < n; ++i) {
      for (j = 0; j < n; ++j) {
        if (edge[i][j] != 0) k++;
      }
    }
    double K = (double)k*1.0/2.0, N = (double)n*1.0;
    printf("%.3f\n", K/N);
  }

  return 0;
}

这题目当初没读懂题意，也想复杂了。。。关键是样例都没有看完，o(╯□╰)o 刚才交了，这题过了。 Friends 题目链接：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5002


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
int edge[120][120];
int main(void){
#ifndef ONLINE_JUDGE
  freopen("zoj5002.in", "r", stdin);
#endif
  int t, n, m, k, i, j, sum, a, b, cnt;
  bool flag;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%d", &n, &m, &k); cnt = 0;
    memset(edge, 0, sizeof(edge));
    for (i = 0; i < m; ++i) {
      scanf("%d%d", &a, &b); edge[a][b] = edge[b][a] = 1;
    }
    flag = false;
    for (i= 0; i < n; ++i) {
      for (j = 0; j < n; ++j) {
        if (i == j) continue;
        if (edge[i][j] == 1) continue;
        sum = 0;
        for (int z = 0; z < n; ++z) {
          if (edge[i][z]==1 && edge[j][z]==1) sum++;
          if (sum >= k) break;
        }
        if (sum >= k) {
          edge[i][j] = edge[j][i] = 1; cnt++;
          i = -1;
          break;
        }
      }
      if (flag) break;
    }
    printf("%d\n", cnt);
  }

  return 0;
}

　　这题当初真的是因为想复杂了，，，唉，因为范围只有100，所以应该可以暴力吧……所以，以后做题首先注意数据范围！　　这题目刚刚交了一下，WA了一次，然后发现一个比较有意思的细节，就是48行，新确定一个关系就要从头开始再找一次，哈哈，还好自己很快就注意到这个东西，不过代码确实比较挫……700+ms过的……

Read more