首页分享 [国家集训队]部落战争

[国家集训队]部落战争

来源：花匠小妙招时间：2024-12-17 08:30

题目描述
lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。

A国是一个M*N的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们约定：

每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。

如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。

每支军队都可以在任意一个城镇停止征战。

所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走12的路线，而他们只能走RC的路线。

lanzerb的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。

输入格式
第一行包含4个整数M、N、R、C，意义见问题描述。接下来M行每行一个长度为N的字符串。如果某个字符是’.’，表示这个地方是城镇；如果这个字符时’x’，表示这个地方是高山深涧。

输出格式
输出一个整数，表示最少的军队个数。

输入输出样例
输入 #1 复制
3 3 1 2
…
.x.
…
输出 #1 复制
4
输入 #2 复制
5 4 1 1
…
…x.
…x
…
x…
输出 #2 复制
5

很明显的最小路径覆盖（而且是不相交路径），所以直接跑最大流即可。答案就是点数减去最大流。

AC代码：

#pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; const int inf=0x3f3f3f3f; const int N=10010,M=100010; int m,n,r,c,s,t,base,h[N],res; int head[N],nex[M],to[M],w[M],tot=1; char g[55][55]; inline void ade(int a,int b,int c){to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot; } inline void add(int a,int b,int c){ade(a,b,c);ade(b,a,0); } inline int id(int x,int y){return m*(x-1)+y; } int bfs(){queue<int> q;q.push(s);memset(h,0,sizeof h);h[s]=1;while(q.size()){int u=q.front();q.pop();for(int i=head[u];i;i=nex[i]){if(w[i]&&!h[to[i]]){h[to[i]]=h[u]+1;q.push(to[i]);}}}return h[t]; } int dfs(int x,int f){if(x==t)return f;int fl=0;for(int i=head[x];i&&f;i=nex[i]){if(h[to[i]]==h[x]+1&&w[i]){int mi=dfs(to[i],min(w[i],f));w[i]-=mi;w[i^1]+=mi;f-=mi;fl+=mi;}}if(!fl)h[x]=-1;return fl; } int dinic(){int res=0;while(bfs())res+=dfs(s,inf);return res; } signed main(){cin>>n>>m>>r>>c;s=0;t=n*m*2+1;base=n*m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>g[i][j];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(g[i][j]=='x')continue;res++;add(s,id(i,j),1);add(id(i,j)+base,t,1);if(i+r<=n&&j-c>=1)add(id(i,j),id(i+r,j-c)+base,1);if(i+r<=n&&j+c<=m)add(id(i,j),id(i+r,j+c)+base,1);if(i+c<=n&&j-r>=1)add(id(i,j),id(i+c,j-r)+base,1);if(i+c<=n&&j+r<=m)add(id(i,j),id(i+c,j+r)+base,1);}}cout<<res-dinic()<<endl;return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263