国家集训队2008论文集

ACM2008国家集训队论文，有益于你对各个算法的学习，升华

#include 
#include 
#include 
#define MAXN 1000
#define MAXM 1000
#define Eps 1e-8
const int dx[4] = {0 1 0 -1};
const int dy[4] = {1 0 -1 0};
int N M P Q;
int map[MAXN][MAXM];
int size[MAXN*MAXM] pos[MAXN*MAXM] bl[MAXN*MAXM] fa[MAXN * MAXM];
double V[MAXN*MAXM] ans;
int list[MAXN*MAXM][2];
int bfs（int stx int sty int ID int height） {
  int head = 0 tail = 1 x y;
  bl[map[stx][sty]] = ID;
  list[0][0] = stx; list[0][1] = sty;
  while （head < tail） {
    size[ID] += height - map[list[head][0]][list[head][1]];
    for （int i = 0; i < 4; i ++） {
      x = list[head][0] + dx[i];
      y = list[head][1] + dy[i];
      if （x >= 0 && x < N && y >= 0 && y < M && bl[map[x][y]] == -1 && map[x][y] < height） {
        list[tail][0] = x;
        list[tail][1] = y;
        bl[map[x][y]] = ID;
        tail ++;
      }
    }
    head ++;
  }
  return 0;
}
int pour（int k） {
  int cnt = 0 t;
  int px = pos[k] / M py = pos[k] % M;
  bool lower[4];
  double rest = 0;
  memset（lower 0 sizeof（lower））;
  for （int i = 0; i < 4; i ++） {
    if （px + dx[i] < 0 || px + dx[i] == N || py + dy[i] < 0 || py + dy[i] == M） {
      cnt ++;
    } else {
      t = map[px + dx[i]][py + dy[i]];
      if （t < k && （fa[bl[t]] != k || V[bl[t]] < size[bl[t]] - Eps）） {
        cnt ++;
        lower[i] = true;
      }
    }
  }
  for （int i = 0; i < 4; i ++） {
    if （px + dx[i] < 0 || px + dx[i] == N || py + dy[i] < 0 || py + dy[i] == M） {
      ans += V[bl[k]] / cnt;
    } else {
      t = map[px + dx[i]][py + dy[i]];
      if （lower[i]） {
        V[bl[t]] += V[bl[k]] / cnt;
      }
      if （fa[bl[t]] == k && V[bl[t]] > size[bl[t]]） {
        rest += V[bl[t]] - size[bl[t]];
        V[bl[t]] = size[bl[t]];
      }
    }
  }
  V[bl[k]] = rest;
  return 0;
}
bool can（int x int y） {
  if （x == 0 || x == N - 1 || y == 0 || y == M - 1） return true;
  for （int i = 0; i < 4; i ++） {
    if （bl[map[x + dx[i]][y + dy[i]]] != -1） return true;
  }
  return false;
}
int main（） {
  int v1 v2 v3 px py x y;
  freopen（“fg.in“ “r“ stdin）;
  freopen（“fg.out“ “w“ stdout）;
  scanf（“%d%d“ &N &M）;
  for （int i = 0; i < N; i ++） {
    for （int j = 0; j < M; j ++） {
      scanf（“%d“ &map[i][j]）;
      map[i][j] --;
      pos[map[i][j]] = i * M + j;
    }
  }
  memset（bl 255 sizeof（bl））;
  memset（fa 255 sizeof（fa））;
  for （int i = 0; i < N * M; i ++） {
    px = pos[i] / M;
    py = pos[i] % M;
    if （can（px py）） {
      bl[i] = P ++;
      for （int j = 0; j < 4; j ++） {
        x = px + dx[j]; 
        y = py + dy[j];
        if （x >= 0 && x < N && y >= 0 && y < M && bl[map[x][y]] == -1 && map[x][y] < i） {
          fa[P] = i;
          bfs（x y P ++ i）;
        }
      }
    }
  }
  scanf（“%d“ &Q）;
  for （int i = 0; i < Q; i ++） {
    scanf（“%d%d%d“ &v1 &v2 &v3）;
    v1 --; v2 --;
    V[bl[map[v1][v2]]] += v3;
  }
  for （int i 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       7673  2008-02-02 15:05  国家集训队2008论文集\content.txt

     文件      24064  2008-01-22 07:55  国家集训队2008论文集\Day1\1.曹钦翔《数据结构的提炼与压缩》\封面.doc

     文件     645632  2008-01-23 16:41  国家集训队2008论文集\Day1\1.曹钦翔《数据结构的提炼与压缩》\数据结构的提炼与压缩.ppt

     文件      30720  2008-01-21 14:50  国家集训队2008论文集\Day1\1.曹钦翔《数据结构的提炼与压缩》\目录.doc

     文件     677888  2008-01-21 14:51  国家集训队2008论文集\Day1\1.曹钦翔《数据结构的提炼与压缩》\论文.doc

     文件     199407  2008-01-26 17:33  国家集训队2008论文集\Day1\10.俞华程《矩阵乘法在信息学中的应用》\slide.pdf

     文件     179455  2008-01-26 17:33  国家集训队2008论文集\Day1\10.俞华程《矩阵乘法在信息学中的应用》\矩阵乘法.pdf

     文件       2188  2008-01-06 17:15  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\catch.dpr

     文件       3753  2007-12-11 15:29  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\pku2103.dpr

     文件       7651  2007-11-21 21:24  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\pku3237.dpr

     文件        237  2007-12-24 21:32  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\gen.dpr

     文件       1653  2007-12-24 22:35  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_10.dpr

     文件        936  2007-12-25 14:42  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_10.txt

     文件       1849  2007-12-24 22:51  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_10_10.dpr

     文件        899  2007-12-25 14:43  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_10_10.txt

     文件       1657  2007-12-24 22:40  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_20.dpr

     文件        911  2007-12-25 14:46  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_20.txt

     文件       1849  2007-12-25 14:56  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_20_10.dpr

     文件       1005  2007-12-25 15:00  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_20_10.txt

     文件       1657  2007-12-24 22:45  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_50.dpr

     文件        895  2007-12-25 15:05  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_50.txt

     文件       1847  2007-12-25 14:11  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_5_10.dpr

     文件        890  2007-12-25 14:42  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_5_10.txt

     文件       1845  2007-12-25 14:09  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_5_5.dpr

     文件        882  2007-12-25 14:33  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099\ural1099_5_5.txt

     文件       1774  2007-11-28 15:03  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\ural1099.dpr

     文件     264192  2008-01-26 12:40  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\平衡规划.doc

     文件     869888  2008-01-26 13:38  国家集训队2008论文集\Day1\2.郑暾《平衡规划——浅析一类平衡思想的应用》\平衡规划.ppt

     文件       7077  2007-11-05 22:30  国家集训队2008论文集\Day1\3.刘弈《浅谈信息学中状态的合理设计与应用》\例题程序\Banal_Tickets.dpr

     文件       7781  2008-01-25 20:26  国家集训队2008论文集\Day1\3.刘弈《浅谈信息学中状态的合理设计与应用》\例题程序\Shoot_Your_Gun.dpr

............此处省略84个文件信息