View Code /* 最小頂點(diǎn)覆蓋：選出最少的點(diǎn)，這些點(diǎn)的關(guān)聯(lián)的邊都被覆蓋 最小頂點(diǎn)覆蓋等于最大匹配*/ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<math.h> using namespace std; const int maxn = 1505; const int inf = 0x7fffffff; struct node{int u,val,next; }edge[ maxn<<2 ]; int head[ maxn ],vis[ maxn ],fa[ maxn ]; int cnt; void init(){memset( head,-1,sizeof(vis) );memset( fa,-1,sizeof(fa) );cnt=0; } void addedge( int a,int b,int c ){edge[ cnt ].u=b;edge[ cnt ].val=c;edge[ cnt ].next=head[ a ];head[ a ]=cnt++; }int dfs( int x ){ // int u=head[ x ];for( int i=head[ x ];i!=-1;i=edge[i].next ){int u=edge[ i ].u;if( vis[ u ]==0 ){vis[ u ]=1;if( fa[ u ]==-1 || dfs( fa[u] ) ){fa[ u ]=x;return 1;}}}return 0; }int main(){int n;while( scanf("%d",&n)!=EOF ){char s[ 2001 ];init();for( int i=0;i<n;i++ ){int a,b,c;int tmp;scanf("%d:(%d)",&a,&tmp);while( tmp-- ){scanf("%d",&b);addedge( a,b,1 );addedge( b,a,1 );}}int ans=0;for( int i=0;i<n;i++ ){if( head[ i ]==-1 ) continue;memset( vis,0,sizeof(vis) );ans+=dfs( i );}printf("%d\n",ans/2);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/xxx0624/archive/2012/12/09/2810004.html

總結(jié)

以上是生活随笔為你收集整理的HDU1054+最小顶点覆盖的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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