一开始TLE了。。
View Code
1 /* 2 dfs+TLE 3 题意：给定一些点，求最多能放多少个点，使得这些放的点不互相攻击 4 5 */ 6 #include<stdio.h> 7 #include<string.h> 8 #include<stdlib.h> 9 #include<algorithm> 10 #include<iostream> 11 #include<queue> 12 #include<vector> 13 #include<map> 14 #include<math.h> 15 typedef long long ll; 16 //typedef __int64 int64; 17 const int maxn = 105; 18 const int maxm = 1005; 19 const int inf = 0x7FFFFFFF; 20 const double pi = acos(-1.0); 21 const double eps = 1e-8; 22 using namespace std; 23 int row[ maxn ],col[ maxn ];//该行该列能否放车 24 int ans_num; 25 struct node2{ 26 int x,y; 27 }Node[ 10005 ];//存储能放车的点 28 int CNT[ maxn ][ maxn ]; 29 30 struct node{ 31 int x[ 24 ],y[ 24 ]; 32 }solve[ maxm ];//每个方案数的具体方法 33 34 int cnt ;//记录有ansnum个车的方案数 35 36 void init(){ 37 //ans_num = 0; 38 memset( row,0,sizeof( row ) ); 39 memset( col,0,sizeof( col ) ); 40 } 41 42 void dfs( int now,int k,int sum ){ 43 for( int i=now;i<k;i++ ){ 44 if( row[ Node[i].x ]==0&&col[ Node[i].y ]==0 ){ 45 row[ Node[i].x ] = 1; 46 col[ Node[i].y ] = 1; 47 if( sum+1>ans_num ) ans_num = sum+1; 48 //printf("sum1 = %d\n",sum); 49 dfs( now+1,k,sum+1 ); 50 row[ Node[i].x ] = 0; 51 col[ Node[i].y ] = 0; 52 } 53 } 54 return ; 55 } 56 57 void dfs2( int now,int k,int sum ){ 58 if( sum==ans_num ){ 59 //printf("sum = %d\n",sum); 60 int f = -1; 61 for( int j=0;j<sum;j++ ){ 62 if( solve[cnt].x[j]==-1||solve[cnt].y[j]==-1 ) { 63 f = 1; 64 break; 65 } 66 //CNT[ solve[cnt].x[j] ][ solve[cnt].y[j] ] ++; 67 //printf("%d %d\n",solve[cnt].x[j],solve[cnt].y[j]); 68 } 69 if( f==-1 ) { 70 71 //printf("sum = %d\n",sum); 72 for( int j=0;j<sum;j++ ){ 73 CNT[ solve[cnt].x[j] ][ solve[cnt].y[j] ] ++; 74 //printf("%d %d\n",solve[cnt].x[j],solve[cnt].y[j]); 75 } 76 77 cnt++ ; 78 } 79 return ; 80 } 81 for( int i=now;i<k;i++ ){ 82 if( row[ Node[i].x ]==0&&col[ Node[i].y ]==0 ){ 83 row[ Node[i].x ] = 1; 84 col[ Node[i].y ] = 1; 85 int tmp = cnt; 86 solve[ tmp ].x[ sum ] = Node[i].x; 87 solve[ tmp ].y[ sum ] = Node[i].y; 88 //printf("sum2 = %d\n",sum+1); 89 dfs2( now+1,k,sum+1 ); 90 solve[ tmp ].x[ sum ] = -1; 91 solve[ tmp ].y[ sum ] = -1; 92 row[ Node[i].x ] = 0; 93 col[ Node[i].y ] = 0; 94 } 95 } 96 return ; 97 } 98 99 int main(){ 100 int n,m,k; 101 int ca = 1; 102 while( scanf("%d%d%d",&n,&m,&k)==3 ){ 103 int a,b; 104 for( int i=0;i<k;i++ ){ 105 scanf("%d%d",&Node[i].x,&Node[i].y); 106 } 107 init(); 108 ans_num = 0; 109 dfs( 0,k,0 );//求出最多能放多少个车 110 if( ans_num==0 ){ 111 printf("Board %d have 0 important blanks for 0 chessmen.\n",ca++); 112 continue; 113 } 114 //printf("ans_sum:%d\n\n\n",ans_num); 115 cnt = 0;//统计放ansnum个车 有多少种方案 116 init(); 117 memset( CNT,0,sizeof( CNT ) ); 118 for( int i=0;i<maxm;i++ ){ 119 for( int j=0;j<24;j++ ) 120 solve[i].x[j]=solve[i].y[j]=-1; 121 } 122 dfs2( 0,k,0 ); 123 int res = 0; 124 for( int i=0;i<k;i++ ){ 125 if( CNT[Node[i].x][Node[i].y]==cnt ) res++; 126 /*printf("CNT[%d][%d] = %d\n",Node[i].x,Node[i].y,CNT[Node[i].x][Node[i].y]);*/ 127 } 128 printf("Board %d have %d important blanks for %d chessmen.\n",ca++,res,ans_num); 129 } 130 return 0; 131 }
二分图：
行号和列号进行匹配！！！！！！！！！！
View Code
1 /* 2 二分图 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 #include<queue> 10 #include<vector> 11 #include<map> 12 #include<math.h> 13 typedef long long ll; 14 //typedef __int64 int64; 15 const int maxn = 105; 16 const int maxm = 1005; 17 const int inf = 0x7FFFFFFF; 18 const double pi = acos(-1.0); 19 const double eps = 1e-8; 20 using namespace std; 21 int mat[ maxn ][ maxn ]; 22 int mylink[ maxn ],vis[ maxn ]; 23 24 int ans1 ,ans2; 25 26 bool dfs( int u,int n,int m ){ 27 for( int i=1;i<=m;i++ ){ 28 if( vis[ i ] ==-1&&mat[u][i]==1 ){ 29 vis[ i ] = 1; 30 if( mylink[ i ]==-1||dfs( mylink[i],n,m ) ){ 31 mylink[ i ] = u; 32 return true; 33 } 34 } 35 } 36 return false; 37 } 38 39 int max_match( int n,int m ){ 40 memset( mylink,-1,sizeof( mylink ) ); 41 int mylink2[ maxn ]; 42 int sum = 0; 43 for( int i=1;i<=n;i++ ){ 44 memset( vis,-1,sizeof( vis )); 45 if( dfs( i,n,m )==true ) 46 sum++; 47 } 48 for( int i=0;i<maxn;i++ ){ 49 mylink2[ i ] = mylink[ i ]; 50 } 51 52 for( int i=1;i<=m;i++ ){ 53 if( mylink2[i]!=-1 ){ 54 int tx,ty; 55 tx = mylink2[ i ]; 56 ty = i; 57 mat[ tx ][ ty ] = 0; 58 memset( mylink,-1,sizeof( mylink ) ); 59 int tmp_sum = 0; 60 for( int i=1;i<=n;i++ ){ 61 memset( vis,-1,sizeof( vis )); 62 if( dfs( i,n,m )==true ) 63 tmp_sum++; 64 } 65 if( tmp_sum!=sum ) ans1++; 66 mat[ tx ][ ty ] = 1; 67 } 68 } 69 //对于已经选定的一种放车方案，分别 去掉 这种方案中的某个棋子，再看能否得到答案 70 return sum; 71 } 72 73 int main(){ 74 int n,m,k; 75 int ca = 1; 76 while( scanf("%d%d%d",&n,&m,&k)==3 ){ 77 memset( mat,0,sizeof( mat )); 78 while( k-- ){ 79 int a,b; 80 scanf("%d%d",&a,&b); 81 mat[ a ][ b ] = 1; 82 } 83 ans1 = 0; 84 ans2 = max_match( n,m ); 85 printf("Board %d have %d important blanks for %d chessmen.\n",ca++,ans1,ans2); 86 } 87 return 0; 88 }