锐客网

  1. 首页 > it技术 > >

graphs|hdu1845 Jimmy’s Assignment --- 完备匹配

题意：
要求在一个特殊的图上找最大匹配，该图特点是：无向图，每个节点度数为3，是一个边双连通分量（the graph is 2-edge-connected (that is, at least 2 edges need to be removed in order to make the graph disconnected) 这一点是这样理解的把。。）
思路：
一般想法就直接建图求最大匹配，点的范围是5000，不优化可能超时，下面代码是890ms过的。


另一种思路：
完备匹配的条件：

1. G是K（K>0）次正则二分图
【graphs|hdu1845 Jimmy’s Assignment --- 完备匹配】2.G是无桥的三次正则图

3.G在去掉任意一个顶点子集S后，其子图中含顶点数为奇数的连通分支数不大于|S|
具有以上三个特征的图一定有完备匹配。且其中第三点是完备匹配的充要条件。
据此可得，题目中所给的图一定是完备匹配，答案是n/2。




#include #include #include #include #include #include #include #include const int maxn=5010; using namespace std; int main() { int n,a,b,t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0; i<3*n/2; i++) scanf("%d%d",&a,&b); printf("%d\n",n/2); } return 0; }




#include #include #include #include #include #include #include #include const int maxn=5010; using namespace std; int mx[maxn],my[maxn],n; bool vis[maxn]; vector e[maxn]; int path(int i) { int j,sz=e[i].size(); for(j=0; j




    推荐阅读


    上一篇：绘制左右翻转的图片

    下一篇：BLE-NRF51822教程5-静态密码设置