0分wa 不知道为啥。。。 有大佬能看出来嘛
查看原帖
0分wa 不知道为啥。。。 有大佬能看出来嘛
292677
Lqingyi楼主2021/5/27 23:09
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<utility>
#define INF 0x3f3f3f3f

using namespace std;

const int N = 810,M = N * N * 2,G = 25;

int head[N],to[M],last[M],w[M],cnt = 1;
void add(int a,int b,int c){
    to[++cnt] = b;
    w[cnt] = c;
    last[cnt] = head[a];
    head[a] = cnt;
    to[++cnt] = a;
    w[cnt] = 0;
    last[cnt] = head[b];
    head[b] = cnt;
}
int n,m,d,S,T;
char a[G][G],b[G][G];
int id[G][G];

int dist[N],cur[N];
bool bfs(){
    memset(dist,0,sizeof dist);
    queue<int>q;
    q.push(S);
    cur[S] = head[S],dist[S] = 1;
    while(q.size()){
        int p = q.front();
        q.pop();
        for(int i = head[p]; i != -1; i = last[i]){
            int j = to[i];
            if(!dist[j] && w[i]){
                dist[j] = dist[p] + 1;
                cur[j] = head[j];
                q.push(j);
            }
        }
    }

    return dist[T] > 0;
}

int dfs(int x,int sum){
    int used = 0;
    if(x == T) return sum;
    for(int i = cur[x]; i != -1; i = last[i]){
        int j = to[i];
        cur[x] = i;
        if(w[i] && dist[j] == dist[x] + 1){
            int dd = dfs(j,min(sum - used,w[i]));
            used += dd;
            w[i] -= dd;
            w[i ^ 1] += dd;
        }
    }

    if(used == 0) dist[x] = -1;
    return used;
}

int dinic(){
    int sum = 0;
    while(bfs()){
        sum += dfs(S,INF);
    }

    return sum;
}

int main(){
    cin >> n >> m >> d;
    int ans = 0 ;
    S = 0;
    for(int i = 1; i <= n; i++){
        getchar();
        for(int j = 1; j <= m; j++){
            scanf("%c",&a[i][j]);
            id[i][j] = ++ans;
        }
    }

    int s = 0;
    memset(head,-1,sizeof head);
    for(int i = 1; i <= n; i++){
        getchar();
         for(int j = 1; j <= m; j++){
            scanf("%c",&b[i][j]);
            if(b[i][j] == 'L') add(S,id[i][j],1),++s;
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            add(id[i][j],id[i][j] + ans,(int)a[i][j] - '0');
        }
    }

    T = ans * 2 + 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i - d <= 0 || j - d <= 0 || i + d > n || j + d > m){
                add(id[i][j] + ans,T,INF);
            }
            for(int k = 1; k <= n; k++){
                for(int l = 1; l <= m; l++){
                    if(i == k && j == l) continue;
                    if((i - k) * (i - k) + (j - l) * (j - l) <= d * d){
                        add(id[i][j] + ans,id[k][l],INF);
                    }
                }
            }
        }
    }


    cout << s - dinic() << endl;





    return 0;
}

2021/5/27 23:09
加载中...