SCU 4531 Cruel War II（DFS）

SCU 4531 Cruel War II（DFS）

题目链接：点击打开链接

题目大意：选出若干个点，每个点会覆盖连接该点的边，使用不大于10切最小的点覆盖整张图。

解题思路：

题目是一般图最小点覆盖问题，直接搞的话。。。我不会。但是这道题要求了如果点数大于10，就输出字符串。所以就可以进行暴力DFS，对于某条没有点覆盖的边，选中左边或选中右边，进行下一次DFS，成熟最多也只有10层，也就是2^10。所以直接暴力DFS枚举点。

#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define FIN freopen(&#", "r", stdin);
#define FOUT freopen(&#", "w", stdout);
#define lson l, mid, cur << 1
#define rson mid + 1, r, cur << 1 | 1
const int INF = 0x3f3f3f3f;
const int MAXN = 1e3 + 50;
const int MAXM = 2e3 + 50;
const int MOD = 1e9 + 7;int n, m, flag;
bool vis[MAXM];struct Edge
{int from, to, nxt;
}E[MAXM];
int Head[MAXN], tot;void edge_init()
{tot = 0;memset(Head, -1, sizeof(Head));
}void edge_add(int u, int v)
{E[tot].from = u;E[tot].to = v;E[tot].nxt = Head[u];Head[u] = tot++;
}void dfs(int step, int start)
{if (step > 10 || step > flag)return;bool cclear = true;for (int i = start; i < m; i++){if (vis[E[i].from] || vis[E[i].to])continue;cclear = false;vis[E[i].from] = true;dfs(step + 1, i + 1);vis[E[i].from] = false;vis[E[i].to] = true;dfs(step + 1, i + 1);vis[E[i].to] = false;break; //如果找到没有覆盖的边，覆盖后直接break，因为如果当前边没有覆盖，后面的边覆盖也没有意义。不break的话会TLE。}if (cclear)flag = min(flag, step);
}int main()
{
#ifndef ONLINE_JUDGEFIN;
#endif // ONLINE_JUDGEint tcase;scanf("%d", &tcase);for (int c = 1; c <= tcase; c++){flag = INF;memset(vis, false, sizeof(vis));scanf("%d%d", &n, &m);edge_init();for (int i = 0; i < m; i++){int f, t;scanf("%d%d", &f, &t);edge_add(f, t);}dfs(0, 0);if (flag == INF)printf("Poor lcyn");elseprintf("%dn", flag);}return 0;
}