竞赛讨论区 > dfs wa了大佬们帮帮我
头像
SSDUT_cyq
编辑于 2020-02-29 08:54
+ 关注

dfs wa了大佬们帮帮我

dfs wa了大佬们帮帮我
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f 
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 10005
#define P pair<int,int>
using namespace std;
int k, q;
ll ans = 0;
ll temp;
int n, m;
int vis[50];
int vis1[50];
int mp[50][50];
int mp1[50][50];
int mp2[50][50];
void dfs(int x)
{
	if (x == min(k, q))
		ans = max(ans, temp);
	else if (x > min(k, q))
		return;
	else
	{
		for (int i = 0; i < n + m; i++)
		{
			if (i < n)
			{
				if (!vis[i])
				{
					vis[i] = 1;
					int temp1 = temp;
					for (int j = 0; j < m; j++)
					{
						temp += mp[i][j];
						mp1[i][j] = mp[i][j];
						mp[i][j] = 0;
					}
					dfs(x + 1);
					vis[i] = 0;
					for (int j = 0; j < m; j++)
					{
						mp[i][j] = mp1[i][j];
						temp -= mp[i][j];
						
					}
				}
			}
			else
			{
				if (!vis1[i-n])
				{
					vis1[i-n] = 1;
					for (int j = 0; j < m; j++)
					{
						temp += mp[j][i-n];
						mp2[j][i - n] = mp[j][i - n];
						mp[j][i-n] = 0;
					}
					dfs(x + 1);
					vis1[i-n] = 0;
					for (int j = 0; j < m; j++)
					{
						mp[j][i-n] = mp2[j][i-n];
						temp -= mp[j][i-n];

					}
				}
			}
		}
		
	}
}
int main()
{
	cin >> n >> m >> k;     q = min(n, m);     for (int i = 0; i < n; i++)         for (int j = 0; j < m; j++)             cin >> mp[i][j];     dfs(0);     cout << ans << endl;


}


全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐