【傳送門：BZOJ2150】

---

簡(jiǎn)要題意：

　　給出一個(gè)矩陣，矩陣上的字符有兩種，一種是'x'，表示山洞（不可走），一種是'.'，表示城鎮(zhèn)

　　可以在城鎮(zhèn)處放士兵，士兵經(jīng)過的每個(gè)城鎮(zhèn)都會(huì)被占領(lǐng)，士兵只能向下走，而且行走的方式和馬相似，不過馬走的是1*2，士兵走的是R*C，士兵不能經(jīng)過一個(gè)被占領(lǐng)的城鎮(zhèn)

　　求出最少派出多少個(gè)士兵能夠占領(lǐng)所有城鎮(zhèn)

---

題解：

　　最小路徑覆蓋問題，用二分圖匹配

　　將所有城鎮(zhèn)拆成兩個(gè)集合

　　如果x能走到y(tǒng)，則x連向y的第二個(gè)集合的點(diǎn)

　　然后將總點(diǎn)數(shù)-最大匹配數(shù)就是最小路徑覆蓋數(shù)了

---

參考代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; char st[51][51]; struct node {int x,y,next; }a[21000];int len,last[6100]; void ins(int x,int y) {len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len; } int dx[5],dy[5]; int n,m,r,c; int p(int x,int y){return (x-1)*m+y;} int match[6100],chw[6100]; bool findmuniu(int x,int t) {for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(chw[y]!=t){chw[y]=t;if(match[y]==0||findmuniu(match[y],t)==true){match[y]=x;return true;}}}return false; } int main() {scanf("%d%d%d%d",&n,&m,&r,&c);for(int i=1;i<=n;i++) scanf("%s",st[i]+1);len=0;memset(last,0,sizeof(last));dx[1]=r;dy[1]=-c;dx[2]=r;dy[2]=c;dx[3]=c;dy[3]=-r;dx[4]=c;dy[4]=r;int sum=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(st[i][j]=='.'){sum++;for(int k=1;k<=4;k++){int tx=i+dx[k],ty=j+dy[k];if(tx<1||ty<1||tx>n||ty>m||st[tx][ty]=='x') continue;ins(p(i,j),p(tx,ty)+n*m);}}}}memset(chw,0,sizeof(chw));memset(match,0,sizeof(match));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(st[i][j]=='.'){int t=p(i,j);if(findmuniu(t,t)==true) sum--;}}}printf("%d\n",sum);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Never-mind/p/8630246.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ2150: 部落战争的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。