刚开始以为是覆盖点,,,后来才发现原来是覆盖边,,汗,错了这么多次
我写了两种方法,,其实还可以用二分图匹配写的,,就没写了
第一种方法是分治法,,具体是这样的
我们设计一个函数,能求出当i为根节点时候的子树中,i放士兵时,整个子树士兵最小数量,以及i不放士兵时,整个子树士兵最小数量
那么通过求子树的答案,然后把答案合并到根节点呢
设根节点放士兵的最小数量为a,不放士兵的最小数量为b
那么对于b,说明子树的根必须都要放士兵才行,所以b+=子节点的a
对于a,因为本身已经放了,所以子树放什么都不是很重要,所以a+=min(子节点的a,子节点的b),最后再加1(在自己的根放了一个)
最后的答案就是在a,b中取最小值了
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1500 + 5;
const int INF = 0x3f3f3f3f;vector<int>G[MX];
int vis[MX];void solve(int u, int &a, int &b) {a = 0;b = 1;for(int i = 0; i < G[u].size(); i++) {int v = G[u][i];int na, nb;solve(v, na, nb);a += nb;b += min(na, nb);}
}int main() {int n;//freopen("input.txt","r",stdin);while(~scanf("%d", &n)) {memset(vis, 0, sizeof(vis));for(int i = 0; i <= n; i++) {G[i].clear();}for(int i = 0; i < n; i++) {int u, v, num;scanf("%d:(%d)", &u, &num);for(int j = 1; j <= num; j++) {scanf("%d", &v);G[u].push_back(v);vis[v] = 1;}}int root;for(int i = 0; i < n; i++) {if(!vis[i]) {root = i;break;}}int a, b;solve(root, a, b);printf("%d\n", min(a, b));}return 0;
}
可以想象,在入度为0的点,如果让他们不放士兵,那么答案一定不会变差。
所以可以通过这一点按照拓扑序求答案
在更新一个点后,把它的父节点的入度减一,如果此时入度为0了就加入到队列中
如果本身没放士兵,那么父节点必须要放士兵
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1500 + 5;
const int INF = 0x3f3f3f3f;int p[MX], IN[MX], col[MX];int main() {int n;//freopen("input.txt", "r", stdin);while(~scanf("%d", &n)) {memset(IN, 0, sizeof(IN));memset(p, -1, sizeof(p));memset(col, 0, sizeof(col));for(int i = 0; i < n; i++) {int u, v, num;scanf("%d:(%d)", &u, &num);for(int j = 1; j <= num; j++) {scanf("%d", &v);p[v] = u;IN[u]++;}}queue<int>work;for(int i = 0; i < n; i++) {if(p[i] != -1 && !IN[i]) {work.push(i);}}int ans = 0;while(!work.empty()) {int f = work.front();work.pop();ans += col[f];if(p[f] != -1) {int v = p[f];col[v] |= col[f] ^ 1;IN[v]--;if(!IN[v]) {work.push(v);}}}printf("%d\n", ans);}return 0;
}