当前位置: 代码迷 >> 综合 >> 暴搜 bnu51645 ACM Battle
  详细解决方案

暴搜 bnu51645 ACM Battle

热度:39   发布时间:2023-12-14 03:13:04.0

传送门:点击打开链接

题意:一个图,选点,覆盖所有的边。(n <= 1000, m <= 2000),最多只能选10个点。

思路:本身这是一道NPC问题,但是因为最多只能选10个点,所以我们可以暴搜。

重点是暴搜的方法,如果是按照点去暴搜的话,复杂度还是会爆炸。

我们考虑到,每一条边的两个节点中,至少有一个节点会被覆盖。

所以我们按照这个去暴搜,复杂度就只有O(2^10*m),十分的神奇!

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 2e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;int n, m;
int P[MX][2], cnt[MX];
int DFS(int c, int s) {if(c > 10) return INF;if(s == m) return c;int e, ans = INF;for(int i = 1; i <= m; i++) {if(!cnt[i]) {e = i; break;}}for(int i = 0; i <= 1; i++) {int u = P[e][i], ns = s;for(int j = 1; j <= m; j++) {if(P[j][0] == u || P[j][1] == u) {cnt[j]++; if(cnt[j] == 1) ns++;}}ans = min(ans, DFS(c + 1, ns));for(int j = 1; j <= m; j++) {if(P[j][0] == u || P[j][1] == u) {cnt[j]--;}}}return ans;
}
int main() {int T; //FIN;scanf("%d", &T);while(T--) {scanf("%d%d", &n, &m);memset(cnt, 0, sizeof(cnt));for(int i = 1; i <= m; i++) {scanf("%d%d", &P[i][0], &P[i][1]);}int ans = DFS(0, 0);if(ans > 10) printf("GG\n");else printf("%d\n", ans);}return 0;
}