1066:[SCOI 2007]トカゲ

1066:[SCOI 2007]トカゲ
Time Limit: 1 Sec  
Memory Limit: 162 MB
Submit: 2614  
Solved: 1284
[ Submit][ Status][ Discuss]
Description
r行c列のグリッドマップには高さの異なる石柱があり、いくつかの石柱にはトカゲが立っています.あなたの任務はできるだけ多くのトカゲを境界の外に逃がすことです.各行の各列の隣接する石柱の距離は1であり、トカゲのジャンプ距離はdであり、すなわちトカゲは平面距離がdを超えないいずれかの石柱にジャンプすることができる.石柱は不安定で、トカゲがジャンプするたびに離れた石柱の高さが1(地図の内部に落ちている場合は到達した石柱の高さが変わらない)減少し、その石柱の元の高さが1であればトカゲは離れて消えてしまう.その後他のトカゲは足を踏み入れることができない.いつでも2匹のトカゲが同じ石柱にいることはできない.
Input
第1の挙動の3つの整数r,c,d,すなわち地図の規模と最大ジャンプ距離を入力する.以下rは石竹の初期状態を示し、0は石柱がないことを示し、1~3は石柱の初期高さを示す.以下rはトカゲの位置を表し、「L」はトカゲを表す.トカゲがいないことを示す.
Output
出力は1行のみで、脱出できないトカゲの総数の最小値を含む整数です.
Sample Input
5 8 2 00000000 02000000 00321100 02000000 00000000 ........ ........ ..LLLL.. ........ ........
Sample Output
1
最初のネットストリームは1週間もやった.の
逆アーク容量は0です!逆アーク容量は0です!逆アーク容量は0です!
逆アーク容量は正アークの反対数だと思って書いていました..
233
各石柱を2つの点(入点と出点)に分解し、容量が改石柱の高さに等しいエッジを接続します.
そしてスーパーソースにトカゲがつながっている点
それぞれの石柱の出点で得られる点の入点をつなぎます
飛び出すことができれば、送金先と縁を結んでください.
最后の一発の最大流...
bzoj上dicnic 28 ms,素朴アルゴリズム40 ms

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<map>
using namespace std;
  
const int maxn = 25;
const int INF = 1E9;
  
struct E{
    int flow,cap,from,to;
    E(){}
    E(int flow,int cap,int from,int to) : flow(flow),cap(cap),from(from),to(to) {}
}edgs[maxn*maxn*maxn*maxn*4];
  
int d,n,m,tot = 0,h[maxn][maxn],cur = 0,L[maxn*maxn*2+10],cnt[maxn*maxn*2+10];
int fa[maxn*maxn*2+10],a[maxn*maxn*2+10];
char p[maxn];
bool vis[maxn*maxn*2+10];
  
vector <int> G[maxn*maxn*2+10];
queue <int> q;
  
int num(int x,int y) {return m*(x-1)+y;}
  
void Add(int Num,int cap,int from,int to) {
    G[from].push_back(Num);
    edgs[Num] = E(0,cap,from,to);
}
  
int dis(int A,int B,int C,int D)
{
    int X = (A-C)*(A-C);
    int Y = (B-D)*(B-D);
    return X+Y;
}
  
bool BFS()
{
    memset(vis,0,sizeof(vis));
    memset(L,0,sizeof(L));
    vis[0] = 1; L[0] = 1;
    q.push(0);
    while (!q.empty()) {
        int k = q.front(); q.pop();
        for (int l = 0; l < G[k].size(); l++) {
            E e = edgs[G[k][l]];
            if (vis[e.to] || e.cap - e.flow <= 0) continue;
            vis[e.to] = 1;
            L[e.to] = L[k] + 1; q.push(e.to);
        }
    }
    return vis[n*m*2+1];
}
  
int DFS(int k,int a)
{
    if (a <= 0 || k == n*m*2+1) return a;
    int f,flow = 0;
    for (int &i = cnt[k]; i < G[k].size(); i++) {
        E &e = edgs[G[k][i]];
        if (L[e.to] == L[k]+1 && (f = DFS(e.to,min(e.cap - e.flow,a))) > 0) {
            flow += f;
            e.flow += f;
            a -= f;
            edgs[G[k][i]^1].flow -= f;
            if (a == 0) break;
        }
    }
    return flow;
}
  
void solve() {
    int x = n*m*2+1;
    while (x != 0) {
        edgs[fa[x]].flow += a[n*m*2+1];
        edgs[fa[x]^1].flow -= a[n*m*2+1];
        x = edgs[fa[x]].from;
    }
}
  
int main()
{
    #ifdef YZY  
        freopen("yzy.txt","r",stdin);
    #endif
      
    cin >> n >> m >> d;
    for (int i = 1; i <= n; i++) {
        scanf("%s",1+p);
        for (int j = 1; j <= m; j++)
            h[i][j] = p[j] - '0';
    }
    for (int i = 1; i <= n; i++) {
        scanf("%s",1+p);
        for (int j = 1; j <= m; j++)
            if (p[j] == 'L') {
                ++tot;
                Add(cur++,1,0,num(i,j));
                Add(cur++,0,num(i,j),0);
            }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (h[i][j]) {
                int N = num(i,j);
                Add(cur++,h[i][j],N,N+n*m);
                Add(cur++,0,N+n*m,N);
                if (i + d > n || i - d < 1 || j + d > m || j - d < 1) {
                    Add(cur++,INF,N+n*m,n*m*2+1);
                    Add(cur++,0,n*m*2+1,N+n*m);
                }
                for (int i1 = 1; i1 <= n; i1++)
                    for (int j1 = 1; j1 <= m; j1++)
                        if ((i != i1 || j != j1) && dis(i,j,i1,j1) <= d*d) {
                            if (h[i1][j1]) {
                                int T = num(i1,j1);
                                Add(cur++,INF,N+n*m,T);
                                Add(cur++,0,T,N+n*m);
                            }
                        }
            }
      
    int flow = 0;
    while (BFS()) {
        memset(cnt,0,sizeof(cnt));
        flow += DFS(0,INF);
    }
    /* 
    for (;;) {
        memset(vis,0,sizeof(vis));
        vis[0] = 1; q.push(0);
        bool flag = 0; 
        a[0] = INF;
        while (!q.empty()) {
            int k = q.front(); q.pop();
            for (int l = 0; l < G[k].size(); l++) {
                E e = edgs[G[k][l]];
                if (vis[e.to] || e.cap - e.flow <= 0) continue;
                vis[e.to] = 1;
                fa[e.to] = G[k][l];
                a[e.to] = min(a[k],e.cap - e.flow);
                q.push(e.to);
            }
            if (vis[n*m*2+1]) {
                flow += a[n*m*2+1]; 
                solve();
                flag = 1; 
                while (!q.empty()) q.pop();
                break;
            }
        }
        if (!flag) break;
    }
    */
    cout << tot - flow;
    return 0;
}

逆アーク容量は0です!
逆アーク容量は0です!