【TJOI2016&&HEOI2016】游戏

115 阅读 0 评论 76 点赞

我是靠谱客的博主粗犷电脑，这篇文章主要介绍【TJOI2016&&HEOI2016】游戏，现在分享给大家，希望可以做个参考。

Description

这里写图片描述

Solution

每个炸弹对整行整列都有约束，那么很显然的是二分图最大匹配，行向列连边，说明去了其中的一个就不能再取。
但是这题有软石头和硬石头的限制，怎么办？
我们可以发现有一些区间内是只能放一个炸弹的，那么我们横着把这种块统计出来，竖着再把这种块找出来（为了打着方便，两个#之间可以当做一个块），如果横着的块i和竖着的块j之间的交点是一个空格，那么就连边，说明如果在这两个块的交点放炸弹，只能放一个。
最后匈牙利就可以过了，但是我还是习惯用网络流来求最大匹配23333
秒切！

Code

复制代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define rep(i,a) for(i=first[a];i;i=next[i])
using namespace std;
const int maxn=107,mxx=30007;
int i,j,k,l,t,n,m,ans;
char s[maxn][maxn];
int hk[mxx][3],sk[mxx][3],tot1,tot2;
int first[mxx*2],next[mxx*2],last[mxx*2],chang[mxx*2],num,T;
int d[mxx*2],fan[mxx*2];
bool bz[mxx*2],az;
void add(int x,int y,int z){
    last[++num]=y;next[num]=first[x];first[x]=num;chang[num]=z;fan[num]=num+1;
    last[++num]=x;next[num]=first[y];first[y]=num;chang[num]=0;fan[num]=num-1;
}
bool bfs(){
    int data[mxx*2],head=0,tail=1,i,j,now;
    memset(data,0,sizeof(data));
    memset(d,0,sizeof(d));d[0]=1;
    while(head<tail){
        now=data[++head];
        rep(i,now){
            if(chang[i]&&!d[last[i]]){
                d[last[i]]=d[now]+1;
                data[++tail]=last[i];
            }
        }
    }
    return d[T]!=0;
}
int dinic(int x,int y){
    if(x==T){
        return y;
    }
    int i,j,k=y,p=0;
    rep(i,x){
        if(chang[i]&&d[last[i]]==d[x]+1){
            j=dinic(last[i],min(y,chang[i]));
            if(j>0){
               chang[i]-=j;chang[fan[i]]+=j;
               p+=j;k-=j;
               if(k<=0)break;    
            }
        }
    }
    if(p==0)d[x]=-1;
    return p;
}
int main(){
    //freopen("fan.in","r",stdin);
    scanf("%d%d",&n,&m);
    fo(i,1,n){
        scanf("%s",s[i]+1);
    }
    fo(i,1,n){
        t=l=0;az=0;
        fo(j,1,n){
            if(s[i][j]=='*')az=1;
            if(t&&(s[i][j]=='*'||(s[i][j]=='x'))){
                l=j;continue;
            }
            if(!t&&s[i][j]=='*'||(s[i][j]=='x')){
                t=l=j;continue;
            }
            if(l&&s[i][j]=='#'&&az){
                hk[++tot1][0]=t,hk[tot1][1]=l;hk[tot1][2]=i;
                t=l=0;az=0;    
            }
            else if(s[i][j]=='#'){t=l=0;}
        }
        if(l&&az){hk[++tot1][0]=t,hk[tot1][1]=l;hk[tot1][2]=i;}
    }
    fo(j,1,n){
        t=l=0;az=0;
        fo(i,1,n){
            if(s[i][j]=='*')az=1;
            if(t&&(s[i][j]=='*'||(s[i][j]=='x'))){
                l=i;continue;
            }
            if(!t&&s[i][j]=='*'||(s[i][j]=='x')){
                t=l=i;continue;
            }
            if(l&&s[i][j]=='#'&&az){
                sk[++tot2][0]=t,sk[tot2][1]=l;sk[tot2][2]=j;
                t=l=0;az=0;    
            }
            else if(s[i][j]=='#'){t=l=0;}
        }
        if(l&&az){sk[++tot2][0]=t,sk[tot2][1]=l;sk[tot2][2]=j;}
    }
    fo(i,1,tot1){
        fo(j,1,tot2){
            if(s[hk[i][2]][sk[j][2]]=='*'&&sk[j][2]<=hk[i][1]&&sk[j][2]>=hk[i][0]&&hk[i][2]<=sk[j][1]&&hk[i][2]>=sk[j][0]){
                add(i,tot1+j,1);
            }
        }
    }
    T=tot1+tot2+1;
    fo(i,1,tot1)add(0,i,1);fo(i,1,tot2)add(i+tot1,T,1);
    while(bfs()){
        ans+=dinic(0,0x7fffffff);
    }
    printf("%dn",ans);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define rep(i,a) for(i=first[a];i;i=next[i])
using namespace std;
const int maxn=107,mxx=30007;
int i,j,k,l,t,n,m,ans;
char s[maxn][maxn];
int hk[mxx][3],sk[mxx][3],tot1,tot2;
int first[mxx*2],next[mxx*2],last[mxx*2],chang[mxx*2],num,T;
int d[mxx*2],fan[mxx*2];
bool bz[mxx*2],az;
void add(int x,int y,int z){
    last[++num]=y;next[num]=first[x];first[x]=num;chang[num]=z;fan[num]=num+1;
    last[++num]=x;next[num]=first[y];first[y]=num;chang[num]=0;fan[num]=num-1;
}
bool bfs(){
    int data[mxx*2],head=0,tail=1,i,j,now;
    memset(data,0,sizeof(data));
    memset(d,0,sizeof(d));d[0]=1;
    while(head<tail){
        now=data[++head];
        rep(i,now){
            if(chang[i]&&!d[last[i]]){
                d[last[i]]=d[now]+1;
                data[++tail]=last[i];
            }
        }
    }
    return d[T]!=0;
}
int dinic(int x,int y){
    if(x==T){
        return y;
    }
    int i,j,k=y,p=0;
    rep(i,x){
        if(chang[i]&&d[last[i]]==d[x]+1){
            j=dinic(last[i],min(y,chang[i]));
            if(j>0){
               chang[i]-=j;chang[fan[i]]+=j;
               p+=j;k-=j;
               if(k<=0)break;    
            }
        }
    }
    if(p==0)d[x]=-1;
    return p;
}
int main(){
    //freopen("fan.in","r",stdin);
    scanf("%d%d",&n,&m);
    fo(i,1,n){
        scanf("%s",s[i]+1);
    }
    fo(i,1,n){
        t=l=0;az=0;
        fo(j,1,n){
            if(s[i][j]=='*')az=1;
            if(t&&(s[i][j]=='*'||(s[i][j]=='x'))){
                l=j;continue;
            }
            if(!t&&s[i][j]=='*'||(s[i][j]=='x')){
                t=l=j;continue;
            }
            if(l&&s[i][j]=='#'&&az){
                hk[++tot1][0]=t,hk[tot1][1]=l;hk[tot1][2]=i;
                t=l=0;az=0;    
            }
            else if(s[i][j]=='#'){t=l=0;}
        }
        if(l&&az){hk[++tot1][0]=t,hk[tot1][1]=l;hk[tot1][2]=i;}
    }
    fo(j,1,n){
        t=l=0;az=0;
        fo(i,1,n){
            if(s[i][j]=='*')az=1;
            if(t&&(s[i][j]=='*'||(s[i][j]=='x'))){
                l=i;continue;
            }
            if(!t&&s[i][j]=='*'||(s[i][j]=='x')){
                t=l=i;continue;
            }
            if(l&&s[i][j]=='#'&&az){
                sk[++tot2][0]=t,sk[tot2][1]=l;sk[tot2][2]=j;
                t=l=0;az=0;    
            }
            else if(s[i][j]=='#'){t=l=0;}
        }
        if(l&&az){sk[++tot2][0]=t,sk[tot2][1]=l;sk[tot2][2]=j;}
    }
    fo(i,1,tot1){
        fo(j,1,tot2){
            if(s[hk[i][2]][sk[j][2]]=='*'&&sk[j][2]<=hk[i][1]&&sk[j][2]>=hk[i][0]&&hk[i][2]<=sk[j][1]&&hk[i][2]>=sk[j][0]){
                add(i,tot1+j,1);
            }
        }
    }
    T=tot1+tot2+1;
    fo(i,1,tot1)add(0,i,1);fo(i,1,tot2)add(i+tot1,T,1);
    while(bfs()){
        ans+=dinic(0,0x7fffffff);
    }
    printf("%dn",ans);
}