lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。 A国是一个MN的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们约定： 2. 如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。 3. 每支军队都可以在任意一个城镇停止征战。 4. 所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走12的路线，而他们只能走R*C的路线。 lanzerb的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。
第一行包含4个整数M、N、R、C，意义见问题描述。接下来M行每行一个长度为N的字符串。如果某个字符是’.’，表示这个地方是城镇；如果这个字符时’x’，表示这个地方是高山深涧。
输出一个整数，表示最少的军队个数。
3 3 1 2 … .x. …
5 4 1 1 … …x. …x … x…
4
5
####【数据范围】
100%的数据中，1<=M,N<=50，1<=R,C<=10。
本来在做网络流，然后就莫名其妙地做起了二分图匹配… 那就试试用网络流跑二分图匹配吧… 反正以前都是直接匈牙利算法…
思路: 可以转化一下题目的模型，变成令通过其他城镇占领掉的城镇尽量多。 那么拆点，把一个城镇拆成起点和终点，每个城镇的起点向它走一步所能到达的城镇的终点连边。 这时可以发现，若把每一对匹配理解为某个终点被覆盖，可以代表一旦与它匹配的起点所代表的城镇被覆盖，则这个终点代表的城镇可以被那个城镇的军队覆盖。 那么最大化它，也就是说，求二分图最大匹配，用总点数减去结果，就可以求得答案啦~
#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int N=10009; const int M=1000009; const int Inf=1e9; int s,t; inline int minn(int a,int b){if(a<b)return a;return b;} inline int maxx(int a,int b){if(a>b)return a;return b;} namespace koishi { int to[M],nxt[M],cap[M],beg[N],tot=1; int dis[N]; queue<int> q; inline int init() { tot=1; memset(beg,0,sizeof(beg)); } inline void adde(int u,int v,int w) { to[++tot]=v; nxt[tot]=beg[u]; cap[tot]=w; beg[u]=tot; } inline void add(int u,int v,int w) { adde(u,v,w); adde(v,u,0); } inline bool bfs() { while(!q.empty())q.pop(); for(int i=0;i<=t;i++) dis[i]=-1; dis[s]=1; q.push(s); while(!q.empty()) { int u=q.front();q.pop(); for(int i=beg[u],v;i;i=nxt[i]) if(dis[v=to[i]]==-1 && cap[i]) { dis[v]=dis[u]+1; q.push(v); } } return dis[t]!=-1; } inline int dfs(int u,int mflow) { if(!mflow || u==t) return mflow; int cost=0; for(int i=beg[u],v,f;i;i=nxt[i]) if(dis[v=to[i]]==dis[u]+1 && cap[i]) { f=dfs(v,minn(cap[i],mflow-cost)); cap[i]-=f; cap[i^1]+=f; cost+=f; if(cost==mflow) break; } if(cost==0) dis[u]=0; return cost; } inline int dinic() { int ans=0; while(bfs()) ans+=dfs(s,Inf); return ans; } }; using namespace koishi; int m,n,r,c; char f[59][59]; int dx[4],dy[4]; inline int pos(int i,int j,int ty) { return (i-1)*n*2+(j-1)*2+ty; } inline bool out(int x,int y) { return x<1 || m<x || y<1 || n<y; } int main() { scanf("%d%d%d%d",&m,&n,&r,&c); for(int i=1;i<=m;i++) scanf("%s",f[i]+1); dx[0]=r; dy[0]=c; dx[1]=r; dy[1]=-c; dx[2]=c;dy[2]=r; dx[3]=c;dy[3]=-r; int ans=0; s=m*n*2+5;t=s+1; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(f[i][j]=='.') { ans++; add(s,pos(i,j,0),1); add(pos(i,j,1),t,1); for(int k=0;k<4;k++) if(!out(i+dx[k],j+dy[k]) && f[i+dx[k]][j+dy[k]]=='.') add(pos(i,j,0),pos(i+dx[k],j+dy[k],1),1); } printf("%d\n",ans-dinic()); return 0; } 