題目鏈接：

傳送門

題目大意：

Bob非常享受玩電腦游戲的過程，尤其是策略游戲，但是在有些時候，他因為不能在第一時間找到最佳的策略而十分傷心。 現在，他遇到了一個問題。他必須保衛一個中世紀的城市，有很多道路將整個城市連起來，整體上看上去像一棵樹。Bob需要放置盡可能少的士兵，保衛樹上所有的邊。士兵只能放在節點上，但是卻可以保衛所有與這個節點相鄰的邊。

題目分析：

由于樹本身具有二分圖的性質，所以這里我把樹手動染色轉成二分圖，然后跑最小點覆蓋
（當然也可以樹形dp）

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define N (1500 + 5) using namespace std; inline int read(){int cnt = 0, f = 1; char c;c = getchar();while (!isdigit(c)) {if(c == '-') f = -f;c = getchar();}while (isdigit(c)) {cnt = cnt * 10 + c - '0';c = getchar();}return cnt * f; } int n, nxt[2*N], to[2*N], first[2*N], tot, x, t, y, Float[N], cnt, black, white, ans, match[N]; bool vis[N]; struct node{int x;int y; }edge[N]; void add(int x, int y) {nxt[++tot] = first[x];first[x] = tot;to[tot] = y; } void Dfs(int u){for (register int i = first[u]; i; i = nxt[i]) {int v = to[i];if(!Float[v]) {Float[v] = Float[u] + 1;Dfs(v);}} } void build_map() {memset (first, 0, sizeof(first));memset (nxt, 0, sizeof(nxt));memset (to, 0, sizeof(to));tot = 0;for (register int i = 1; i <= cnt; i++) {int X = edge[i].x; int Y = edge[i].y;if (Float[X] % 2 == 1) {add(X, Y);if (!vis[X]) {vis[X] = true;black++;}if (!vis[Y]) {vis[Y] = true;white++;}} else {add(Y, X);if (!vis[X]) {vis[X] = true;white++;}if (!vis[Y]) {vis[Y] = true;black++;}}} } int find(int u) { // cout<<u<<"##"<<endl;for (register int i = first[u]; i; i = nxt[i]) {int v = to[i]; // cout<<vis[v]<<" "<<v<<endl;if (vis[v]) {continue; } else {vis[v] = true;if (match[v] == -1||find(match[v])) {match[v] = u;return 1;}}}return 0; }int hungary() {for (register int i = 1; i <= n; i++) match[i] = -1;for (register int i = 1; i <= n; i++) {for (register int j = 1; j <= n; j++) vis[j] = 0;ans += find(i);}return ans; }int main(){while(scanf("%d", &n) != EOF) {memset(first, 0, sizeof(first));memset(nxt, 0, sizeof(nxt));memset(to, 0, sizeof(to));memset(Float, 0, sizeof(Float));memset(vis, 0, sizeof(vis));tot=0; cnt=0; ans=0;for (register int i = 1; i <= n; i++) {x = read();t = read();for (register int j = 1; j <= t; j++) {y = read();edge[++cnt].x = x+1;edge[cnt].y = y+1;add(x+1,y+1);add(y+1,x+1);}}Float[1] = 1;Dfs(1);build_map(); // cout<<black<<" "<<white<<endl; // for(register int i = 1; i <= n; i++) cout<<Float[i];int res = hungary();printf("%d\n", res);}return 0; }

轉載于:https://www.cnblogs.com/kma093/p/10540883.html

總結

以上是生活随笔為你收集整理的[POJ1463] Strategic game的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。