D是图G的一个顶点集，对于G的任一顶点U，要么U是D集合的顶点元素，要么U与D集合的某一顶点相邻。那么D称为图G的一个支配集。
若在D中除去任何元素后，D都不再是支配集，则支配集D称为极小支配集。
称D的所有支配集中顶点个数最少的支配集为最小支配集D0。
r(G)=D0中顶点个数。称作G的支配数。
最小支配集一定是极小支配集；
任何一个支配集以一个极小支配集为子集；
G中所含的极小支配集可能有两个以上，而且其顶点个数可以不同。但r(G)是唯一的。
#include<iostream> #include<cstdio> #define INF 0x3F3F3F3F using namespace std;struct EDGE {int v,next; }E[1111111];int ptr[11111],vis[11111],over[11111],Edgenum; int ans,N; int f[11111][3];void addEdge( int u,int v ) {E[Edgenum].v=v;E[Edgenum].next=ptr[u];ptr[u]=Edgenum++; }void dfs( int cur ) {vis[cur]=true;int x=INF,t,s=0,suml=0;for( int i=ptr[cur];i!=-1;i=E[i].next ){if( !vis[E[i].v] ){dfs( E[i].v );t=min( f[E[i].v][0],f[E[i].v][1] );x=min( x,f[E[i].v][1]-t );s+=t; suml+=min( t,f[E[i].v][2] );}}f[cur][0]=s+x;f[cur][1]=suml+1;f[cur][2]=s; }int main() {//freopen( "test.in","r",stdin );//freopen( "test.out","w",stdout );while( scanf( "%d",&N )!=EOF ){int u,v;Edgenum=0;memset( ptr,-1,sizeof(ptr) );memset( vis,0,sizeof(vis) );memset( over,0,sizeof(over) );for( int i=1;i<N;i++ ){scanf( "%d %d",&u,&v );addEdge( u,v );addEdge( v,u );}dfs(1);ans=min(f[1][0],f[1][1]);printf( "%d\n",ans );}return 0; } #include<iostream>
#include<cstdio>
#define INF 0x3F3F3F3F
using namespace std;struct EDGE
{int v,next;
}E[1111111];int ptr[11111],vis[11111],over[11111],Edgenum;
int ans,N;void addEdge( int u,int v )
{E[Edgenum].v=v;E[Edgenum].next=ptr[u];ptr[u]=Edgenum++;
}void dfs( int cur,int fat )
{ bool flag=false;vis[cur]=true;for( int i=ptr[cur];i!=-1;i=E[i].next ){if( vis[E[i].v]==0 ){dfs(E[i].v,cur);flag=flag||over[E[i].v];}}//如果是根节点且孩子节点。孙子节点都未覆盖则此节点+1 if( (fat==-1||!over[fat])&&!flag&&!over[cur] ){over[fat]=true;ans++;}//如果当前节点为根节点,且子节点未被覆盖。
}int main()
{//freopen( "test.in","r",stdin );//freopen( "test.out","w",stdout );while( scanf( "%d",&N )!=EOF ){int u,v;Edgenum=0;memset( ptr,-1,sizeof(ptr) );memset( vis,0,sizeof(vis) );memset( over,0,sizeof(over) );for( int i=1;i<N;i++ ){scanf( "%d %d",&u,&v );addEdge( u,v );addEdge( v,u );}ans=0;dfs( 1,-1 );printf( "%d\n",ans );}
}
刚百度了一下，图的最小支配集为NP难问题....
我去...
难过我根据定义写的dfs超时了....
下面给出我的O(n!)的算法.. 虽然没什么必要...
#include<iostream>
using namespace std;struct EDGE
{int v,next;
}E[1111111];int ptr[11111],vis[11111],Edgenum;
int minT,N;void addEdge( int u,int v )
{E[Edgenum].v=v;E[Edgenum].next=ptr[u];ptr[u]=Edgenum++;
}void dfs( int cur,int layer )
{ for( int i=ptr[cur];i!=-1;i=E[i].next )vis[E[i].v]++;int cnt=0;for( int i=1;i<=N;i++ )if( vis[i] )cnt++;if( cnt==N ){for( int i=ptr[cur];i!=-1;i=E[i].next )vis[E[i].v]--;minT=min(minT,layer);return ;}for( int i=cur+1;i<=N;i++ )if( vis[i]==0 ){vis[i]++;dfs(i,layer+1);vis[i]--;}for( int i=ptr[cur];i!=-1;i=E[i].next )vis[E[i].v]--;
}int main()
{//freopen( "test.in","r",stdin );//freopen( "test.out","w",stdout );minT=0x3FFFFFFF;memset( ptr,-1,sizeof(ptr) );memset( vis,0,sizeof(vis) );int u,v;Edgenum=0; scanf( "%d",&N );while( scanf( "%d %d",&u,&v )!=EOF ){addEdge( u,v );addEdge( v,u );}for( int i=1;i<=N;i++ ){vis[i]++;dfs(i,1);vis[i]--;}printf( "%d\n",minT );
}