Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

郁闷之余发个好看点的。。

Posted by 104GOGO at 2011-10-11 10:20:58 on Problem 3740
In Reply To:暴力完全可以,而且G++更快些,代码如下 Posted by:zhongwen at 2011-10-10 20:27:40
#include <stdio.h>
#include <string.h>

int n,m,vis[305],ar[20][305];

int match()
{
	int i;
	for (i=0;i<m;i++)
	{
		if(vis[i]!=1)return 0;
	}
	return 1;
}

int judge()
{
	int i;
	for (i=0;i<m;i++)
	{
		if(vis[i]>1)return 0;
	}
	return 1;
}

int dfs(int i)
{
	int j,k;
	if (match())return 1;
	for (k=i;k<n;k++)
	{
		for (j=0;j<m;j++)
		{
			vis[j]+=ar[k][j];
		}
		if(judge())if(dfs(k+1))return 1;
		//郁闷啊,太不细心了,这个地方的k一直写成i了,无限TLE
		for (j=0;j<m;j++)
		{
			vis[j]-=ar[k][j];
		}
	}
	return 0;
}

int main()
{
	int i,j;
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		for (i=0;i<n;i++)
			for (j=0;j<m;j++)
				scanf("%d",&ar[i][j]);
		memset(vis,0,sizeof(vis));
		if(dfs(0))printf("Yes, I found it\n");
		else printf("It is impossible\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator