首页 > 代码库 > [bzoj4554] [Tjoi2016&Heoi2016]游戏
[bzoj4554] [Tjoi2016&Heoi2016]游戏
传送门
网络流的题目做的还真不是很多,这种题目很容易看出是网络流,但就是不怎么会建图.
如果没有硬石头,就是一个经典的二分图匹配问题.
但是有硬石头存在,由于硬石头对前后左右的状态不会发生传递,因此,可以以硬石头为界建立联通块.
然后跑网络流就行了.
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<string> #include<iomanip> #include<algorithm> #include<map> using namespace std; #define LL long long #define FILE "dealing" #define up(i,j,n) for(int i=j;i<=n;++i) #define db double #define ull unsigned long long #define eps 1e-10 #define pii pair<int,int> int read(){ int x=0,f=1,ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();} return f*x; } const int maxn=53,maxm=20000,mod=(int)(1e9+7+0.1),limit=(int)(1e6+1),inf=(int)(1e9); int n,m,S,T; char s[53][53]; struct node{ int y,next,flow,rev; }e[maxm]; int len,linkk[maxm]; void insert(int x,int y,int flow){ e[++len].y=y; e[len].next=linkk[x]; linkk[x]=len; e[len].flow=flow; e[len].rev=len+1; e[++len].y=x; e[len].next=linkk[y]; linkk[y]=len; e[len].flow=0; e[len].rev=len-1; } int heng[maxn][maxn],shu[maxn][maxn],cnt1,cnt2; int q[maxm],head,tail,dis[maxm]; bool makelevel(){ head=tail=0; memset(dis,-1,sizeof(dis)); q[++tail]=S;dis[S]=0; while(++head<=tail){ int x=q[head]; for(int i=linkk[x];i;i=e[i].next){ if(e[i].flow&&dis[e[i].y]==-1){ dis[e[i].y]=dis[x]+1; q[++tail]=e[i].y; } } } return dis[T]!=-1; } int makeflow(int x,int flow){ if(x==T)return flow; int maxflow=0,d=0; for(int i=linkk[x];i&&maxflow!=flow;i=e[i].next){ if(e[i].flow&&dis[e[i].y]==dis[x]+1) if(d=makeflow(e[i].y,min(e[i].flow,flow-maxflow))){ maxflow+=d; e[i].flow-=d; e[e[i].rev].flow+=d; } } if(!maxflow)dis[x]=-1; return maxflow; } int ans=0; void dinic(){ int d; while(makelevel()) while(d=makeflow(S,inf)) ans+=d; } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read();m=read();S=0; up(i,1,n)up(j,1,m)scanf(" %c",&s[i][j]); for(int i=1;i<=n;i++){ cnt1++; for(int j=1;j<=n;j++){ if((s[i][j]==‘*‘||s[i][j]==‘x‘)&&s[i][j-1]==‘#‘)cnt1++; if(s[i][j]==‘*‘) heng[i][j]=cnt1; } } cnt2=cnt1; for(int j=1;j<=m;j++){ cnt2++; for(int i=1;i<=n;i++){ if((s[i][j]==‘*‘||s[i][j]==‘x‘)&&s[i-1][j]==‘#‘)cnt2++; if(s[i][j]==‘*‘){ shu[i][j]=cnt2; insert(heng[i][j],shu[i][j],1); } } } T=cnt1+cnt2+1; up(i,1,cnt1)insert(S,i,1); up(i,1,cnt2)insert(i+cnt1,T,1); dinic(); printf("%d\n",ans); return 0; }
[bzoj4554] [Tjoi2016&Heoi2016]游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。