直接暴力建边, 在 lougu 上跑的飞快.(except the last test)
总结一下也就是三句话:
- insert(id(i, j), id(i, j + 1), x)
- insert(id(i, j), id(i + 1, j), x)
- insert(id(i, j), id(i + 1, j + 1), x)
没了就,..dinic 什么的就看看本博客分享的总结爸...
代码当然还是要发的, 即使只是一个暴力..
- #include <map>
- #include <set>
- #include <cmath>
- #include <ctime>
- #include <queue>
- #include <stack>
- #include <vector>
- #include <bitset>
- #include <cstdio>
- #include <cctype>
- #include <string>
- #include <cstring>
- #include <cassert>
- #include <climits>
- #include <cstdlib>
- #include <iostream>
- #include <algorithm>
- #include <functional>
- using namespace std ;
- #define rep(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
- #define Rep(i, a, b) for (int (i) = (a) - 1; (i) <(b); (i)++)
- #define REP(i, a, b) for (int (i) = (a); (i)>= (b); (i)--)
- #define clr(a) memset(a, 0, sizeof(a))
- #define Sort(a, len, cmp) sort(a + 1, a + len + 1, cmp)
- #define ass(a, sum) memset(a, sum, sizeof(a))
- #define ls ((rt) <<1)
- #define rs ((rt) << 1 | 1)
- #define lowbit(x) (x & -x)
- #define mp make_pair
- #define pb push_back
- #define fi first
- #define se second
- #define endl '\n'
- #define ENDL cout << endl
- #define SZ(x) ((int)x.size())
- typedef long long ll ;
- typedef unsigned long long ull ;
- typedef vector <int> vi ;
- typedef pair <int, int> pii ;
- typedef pair <ll, ll> pll ;
- typedef map <int, int> mii ;
- typedef map <string, int> msi ;
- typedef map <ll, ll> mll ;
- const int N = 1010 ;
- const double eps = 1e-8 ;
- const int iinf = INT_MAX ;
- const ll linf = 2e18 ;
- const double dinf = 1e30 ;
- const int MOD = 1000000007 ;
- inline int read(){
- int X = 0, w = 0 ;
- char ch = 0 ;
- while (!isdigit(ch)) { w |= ch == '-' ; ch = getchar() ; }
- while (isdigit(ch)) X = (X <<3) + (X << 1) + (ch ^ 48), ch = getchar() ;
- return w ? - X : X ;
- }
- void write(int x){
- if (x < 0) putchar('-'), x = - x ;
- if (x> 9) write(x / 10) ;
- putchar(x % 10 + '0') ;
- }
- void print(int x) {
- cout <<x << endl ;
- exit(0) ;
- }
- void PRINT(string x) {
- cout << x << endl ;
- exit(0) ;
- }
- void douout(double x){
- printf("%lf\n", x + 0.0000000001) ;
- }
- int n, m, x, top = 1, s, t ;
- int head[N * N], dep[N * N] ;
- struct Edge {
- int to, nxt, w ;
- } e[N * N * 6] ;
- void add(int a, int b, int w) {
- e[++top] = (Edge) {b, head[a], w} ;
- head[a] = top ;
- }
- void insert(int a, int b, int w) {
- add(a, b, w) ;
- add(b, a, w) ;
- }
- bool bfs() { // 分层图
- queue <int> q ;
- q.push(s) ;
- clr(dep) ;
- dep[s] = 1 ;
- while (!q.empty()) {
- int now = q.front() ;
- q.pop() ;
- for (int i = head[now]; i; i = e[i].nxt) {
- int to = e[i].to ;
- if (e[i].w && !dep[to]) {
- dep[to] = dep[now] + 1 ;
- q.push(to) ;
- }
- }
- }
- if (!dep[t]) return 0 ;
- else return 1 ;
- }
- int dfs(int rt, int dis) {
- if (rt == t) return dis ;
- for (int i = head[rt]; i; i = e[i].nxt) {
- int to = e[i].to ;
- if (dep[to] == dep[rt] + 1 && e[i].w) {
- int p = dfs(to, min(e[i].w, dis));
- if (!p) {
- dep[to] = -1;
- continue;
- }
- e[i].w -= p ;
- e[i ^ 1].w += p ;
- return p ;
- }
- }
- return 0 ;
- }
- int dinic() {
- int res = 0 ;
- while (bfs()) {
- while (int d = dfs(s, iinf)) res += d ;
- }
- return res ;
- }
- int id(int x, int y) {
- return (x - 1) * m + y ;
- }
- signed main(){
- scanf("%d%d", &n, &m) ;
- s = 1, t = id(n, m) ;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j < m; j++) {
- scanf("%d", &x) ;
- insert(id(i, j), id(i, j + 1), x) ;
- }
- for (int i = 1; i < n; i++)
- for (int j = 1; j <= m; j++) {
- scanf("%d", &x) ;
- insert(id(i, j), id(i + 1, j), x) ;
- }
- for (int i = 1; i < n; i++)
- for (int j = 1; j < m; j++) {
- scanf("%d", &x) ;
- insert(id(i, j), id(i + 1, j + 1), x) ;
- }
- printf("%d\n", dinic()) ;
- }
- /*
- 写代码时请注意:
- 1. 是否要开 Long Long? 数组边界处理好了么?
- 2. 实数精度有没有处理?
- 3. 特殊情况处理好了么?
- 4. 做一些总比不做好.
- 思考提醒:
- 1. 最大值和最小值问题可不可以用二分答案?
- 2. 有没有贪心策略? 否则能不能 dp?
- */
[BJOI2006] 狼抓兔子 AC CODE
[BJOI2006] 狼抓兔子 暴力 AC 啦!
来源: http://www.bubuko.com/infodetail-2864957.html