正題

---

大意

一個(gè)n*n的矩陣?yán)镉衜個(gè)點(diǎn)，你可以一下打掉一排或以列，求打掉所以點(diǎn)要的最小次數(shù)。
如：
X.X
.X.
.X.
顯然可以看出只需要打兩槍。

---

解題思路

將行和列分為一個(gè)二分圖，然后每個(gè)點(diǎn)的坐標(biāo)講x和y相連。然后求最小點(diǎn)覆蓋

最小點(diǎn)覆蓋=最大匹配

---

代碼

#include<cstdio> #include<cstring> using namespace std; struct line{int to,next; }a[20001]; int xx,yy,n,m,s,link[501],tot,ls[501]; bool cover[501]; void add(int x,int y) {a[++tot].next=ls[x];a[tot].to=y;ls[x]=tot; }//鄰接表 int find(int x)//求最大匹配 {for (int q=ls[x];q;q=a[q].next){if (!cover[a[q].to]){int p=link[a[q].to];link[a[q].to]=x;cover[a[q].to]=true;if (!p || find(p)) return true;link[a[q].to]=p;}}return false; } int main() {scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d",&xx,&yy);add(xx,yy);//鏈接}for (int i=1;i<=n;i++){memset(cover,0,sizeof(cover));if (find(i)) s++;}printf("%d",s); }

總結(jié)

以上是生活随笔為你收集整理的ssl1341-Asteroids【最大匹配,最小点覆盖,图论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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