正題

---

大意

給一個(gè)無(wú)向圖，求最少需要多少條路徑可以連接所有點(diǎn)。

---

解題思路

一個(gè)公式就好了
最小路徑覆蓋數(shù)=最大匹配數(shù)

---

代碼

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

總結(jié)

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

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