锐客网

  1. 首页 > it技术 > >

★ HDU 3118 二分匹配本质题，删除最少的边，使图不存在奇环

题意：给你一幅图，要你删除最少的边，使得图中不存在奇环。


分析：首先想到二分图是不存在奇数环的，又因为n<=15，所以我们可以状态压缩枚举集合，分成X，Y两个集合，然后删除每个集合里面任意两点间的连边，取最小值就是解。


考察二分图的本质啊。。。出题人的这题是很经典啊。。。


代码：

#pragma comment(linker,"/STACK:102400000,102400000") #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; //记得必要的时候改成无符号 const int INF=1000000000; int g[20][20],v[20][20]; int main() { int T,i,x,y,sum,mx,n,m,j,k; int a[20],b[20],sa,sb; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); mx=INF; memset(g,0,sizeof(g)); for(i=1; i<=m; i++){ scanf("%d%d",&x,&y); x++; y++; g[x][y]++; g[y][x]++; } for(i=1; i<(1<



【★ HDU 3118 二分匹配本质题，删除最少的边，使图不存在奇环】

    推荐阅读


    上一篇：苏幕遮

    下一篇：网络流|★ POJ 2516 最小费用最大流（分开计算，K次费用流）