icontofig | 发布于 2019-07-15 17:15:53 | 阅读量 264 | 网络流
发布于 2019-07-15 17:15:53 | 网络流

题解

很明显能看出来同色的格子之间是不会相互攻击的。

于是我们就可以把这张图分成一张二分图了,然后建边跑最大流。

有攻击关系的点需要连一条流量为1的边。

不过值得注意的是,要优化建边方法,不然会超时。

既然是二分图,我们考虑黄色格子代表的点与S连边,红色格子代表的点与T连边,在考虑攻击关系的时候,只从黄色格子连向红色格子就可以了(因为互相攻击,所以是等价的,当然与上述方案完全反过来建边也可以)。

我们要求的是最多的共存骑士,所以是明显的二分图最大独立集的问题,求出的最大流相当于一个最小割,用总数n*n-m再减去这个最小割就是最大独立集的最后剩余的数目。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 205;
struct edge{
    int to,next,cap;
}e[maxn*maxn * 16];
int cnt = 0;
int h[maxn*maxn];
void add(int u,int v,int c){
    e[cnt].to = v;e[cnt].cap = c;e[cnt].next = h[u];
    h[u] = cnt++;
    return;
}
int d[maxn*maxn];
const int INF = 1e9;
bool BFS(int s,int t){
    for(int i = s;i <= t;++i){
        d[i] = INF;
    }
    d[s] = 0;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = h[x];i != -1;i = e[i].next){
            int v = e[i].to;
            if(d[v] == INF && e[i].cap > 0){
                d[v] = d[x] + 1;
                q.push(v);
            }
        }
    }
    return (d[t] != INF);
}
int cur[maxn*maxn];
int DFS(int now,int t,int a){
    if(a == 0 || now == t)return a;
    int flow = 0;
    for(int &i = cur[now];i != -1;i = e[i].next){
        int v = e[i].to;
        if(d[v] == d[now] + 1 && e[i].cap > 0){
            int f = min(a - flow,e[i].cap);
            f = DFS(v,t,f);
            flow += f;
            e[i].cap -= f;
            e[i^1].cap += f;
            if(flow == a)return flow;
        }
    }
    return flow;
}
int dinic(int s,int t){
    int flow = 0;
    while(BFS(s,t)){
        for(int i = s;i <= t;++i)cur[i] = h[i];
        flow += DFS(s,t,INF);
    }
    return flow;
}
int n,m;
int id(int x,int y){
    return (x-1)*n + y;
}
int mp[maxn][maxn];
int x,y;
int S,T;
int main(){
    memset(h,-1,sizeof(h));
    cnt = 0;
    n = get_num();
    m = get_num();
    for(int i = 1;i <= m;++i){
        x = get_num();
        y = get_num();
        mp[x][y] = 1;
    }
    S = 0;
    T = n * n + 1;
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= n;++j){
            if(mp[i][j])continue;
            int idd = id(i,j);
            if((i+j) & 1){
                add(S,idd,1);
                add(idd,S,0);
                for(int l = -2;l <= 2;l += 4){
                    for(int r = -1;r <= 1;r += 2){
                            if(i+l > 0 && i+l <= n && j+r > 0 && j+r <= n){
                                add(idd,id(i+l,j+r),1);
                                add(id(i+l,j+r),idd,0);
                            }
                        }
                }
                for(int l = -1;l <= 1;l += 2){
                    for(int r = -2;r <= 2;r += 4){
                        if(i+l > 0 && i+l <= n && j+r > 0 && j+r <= n){
                            add(idd,id(i+l,j+r),1);
                            add(id(i+l,j+r),idd,0);
                        }
                    }
                }
            }
            else{
                add(idd,T,1);
                add(T,idd,0);
            }
        }
    int p = dinic(S,T);
    printf("%d\n",n*n - m - p);
    return 0;
}



内容更新于: 2019-07-15 17:15:53
链接地址: http://blog.leanote.com/post/icontofig/8f70d99473fa

上一篇: Codeforces Round #2 The least round way DP+贪心

下一篇: BAPC18 I In Case of an Invasion,Please... 最短路+离散化+二分+最大流

264 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航